Та самая задачка
Я уже отчаялась ее решать и решила почитать упомянутое решение Миши Лысова. Ссылка на него вот .
Оно непростое и я в нем еще не разобралась до конца, но собираюсь это сделать. С его разрешения, я копирую его сюда. С удовольствием готова обсуждать частности в комментариях.
Сначала повторю условие.
Алиса и Боб играют против казино. Казино предоставляет произвольную последовательность из 9 нулей и единиц. Боб видит эту последовательность, а Алиса нет. Далее, девять раз повторяется повторяется следующая операция: Алиса говорит 0/1, потом Боб говорит 0/1, потом вскрывается очередная цифра в последовательности, которую предоставило казино. Если все три цифры совпали, то Алиса и Боб выиграли раунд, а иначе проиграли.
Им хочется заранее договориться о стратегии, которая позволит им выиграть хотя бы 6 раундов. Как им это сделать?
Далее будет текст Миши с незначительными поправками. Точнее, его первая часть, в которой мы еще не решим нашу задачу, но немного ее переформулируем и докажем некоторые факты для общего случая.
[Решение]
Будем считать, что раундов всего n (у нас n = 9).
Далее, пусть f(n) - максимальное число раундов из n, которое Алиса с Бобом могут гарантированно угадать (f(9)=6). Тогда я умею доказывать, что существует предел f(n)/n и он лежит между 9/13=0.69.. и 82%.
Итак, теперь о доказательствах и идеях. Начну с доказательства того, что предел f(n)/n есть. Будем доказывать, что эта последовательность стремится к своей верхней грани s. Возьмём любое eps>0. Существует такое n_0, что f(n_0)/n_0 > s - eps/2. Воспользуемся такой стратегией для А. и Б. в произвольном n: разделим все раунды на группы. В первых [n/n_0] группах по n_0 раундов, а в оставшейся n%n_0 раундов. Во всех группах, кроме последней, применим стратегию для n_0, а в последней ходим наобум, то есть ничего не угадываем, нам этого хватит. По такой стратегии мы точно угадаем f(n_0)*[n/n_0] раундов. Понятно, что при такой стратегии доля угаданных будет хотя бы f(n_0) * (n/n_0-1) / n, что стремится к f(n_0)/n_0 при n стремится к бесконечности. Значит с какого-то n_1 доля угаданных больше f(n_0)/n_0-eps/2>s-eps. Мы доказали это для любого eps>0, значит предел f(n)/n равен s. чтд
Теперь покажем простым способом, что этот предел f(n)/n не меньше 2/3. Рассмотрим n вида 3k+1. Разобьём все раунды на группы: первая размера 1, все остальные размера 3. В первом раунде Боб ходит наиболее чаще встречаемом числом из второй группы у казино, а Алиса произвольно. Во второй группе Алиса всегда ходит чаще встречаемым числом, а Боб следующим образом. Если в этой группе у казино 2 числа и одно, то в этих двух числах он ходит ими, а в оставшемся наиболее часто встречающимся у казино в третьей группе. А в случае, если у казино в этой группе 3 одинаковых числа, то в первых двух Боб ходит ими, а в третьем ходит наиболее часто встречающимся из следующей группы. Таким образом Алиса всегда угадает хотя бы 2 из 3 и получит информацию о том, какое число наиболее часто встречаемое в следующей группе. Во всех оставшихся группах повторяем стратегию, как для второй группы, и так гарантированно угадываем 2k из 3k+1.
Таким образом мы получили, что для бесконечной подпоследовательности, а именно n вида 3k+1, искомый предел хотя бы 2/3, а так как у всей последовательности есть предел, то он тоже хотя бы 2/3.
( думаю, если вы получили 5 из 8, то примерно так это и было сделано )
Теперь копнём глубже и переведём задачу на другой язык, который в будущем сможет продемонстрировать в том числе, что 6 из 9 возможно, 7 из 10 невозможно, а искомый предел меньше 82%.
Поставим задачу немного под другим углом: какого наибольшее число g(n,m) строк казино длины n, в которых Алиса и Боб могут так договориться, что точно совершат не более m ошибок из n возможных. Тогда при фиксированном n наименьшее m такое, что g(n,m) = 2^n и будет равно n-f(n). Оценим g(n,m) сверху. В после первого раунда у Алисы будет лишь следующая информация: первое число казино и первый ход Боба. Будем считать, что все игроки ходят детерминировано, потому что для любого вероятностного алгоритма можно взять детерминированный, состоящий из ходов ненулевой вероятности, который будет иметь не меньшее число гарантируемо угадываемых раундов. Таким образом на первом ходу у Алисы не было никакой информации, и она пошла детерминировано, БОО нулём. Далее с точки зрения Алисы все строки казино разбились на 4 группы, которые определяются первыми числами казино и Боба. В трёх из этих групп Алиса ошиблась, а в одной угадала. Внутри каждой группы мы не можем действовать лучше, чем если бы она состояла из каких мы хотим строк длины n-1. Таким образом мы доказали оценку g(n,m)<=g(n-1,m)+3g(n-1,m-1).
Если приглядеться, то это неравенство можно усилить, учтя, что пары групп, соответствующие одинаковым первым раундам казино, в сумме не могут иметь более 2^(n-1) строк казино, потому что именно столько всего строк казино и начинается с одной цифры. Поэтому верно более сильное неравенство:
g(n,m)<=min(g(n-1,m)+g(n-1,m-1), 2^(n-1)) + min(2g(n-1,m-1), 2^(n-1))
Теперь, используя это неравенство, составим таблицу ОЦЕНОК СВЕРХУ на g(n,m), заполняя строки сверху вниз (номер строки n с 1, номер столбца m с 0)
g 0 1 2 3
1 1 2 2 2 ..
2 ? ? ? ?
Надеюсь, содержание первой строки ни у кого вопросов не вызывает. Каждую следующую строку будем заполнять исключительно по предыдущей и доказанному неравенству.
g 0 1 2 3
1 1 2 2 2 ..
2 1 4 4 4 ..
3 1 6 8 8 ..
4 1 9 16 16 ..
5 1 12 32 32 ..
6 1 15 56 64 ..
7 1 18 94 128 ..
8 1 21 148 256 ..
9 1 24 211 512 ..
10 1 27 283 934 ..
..
Поясню например g(3,1). По неравенству оно <= min(4+1, 2^2)+min(1+1,2^2)=4+2=6. Ещё раз скажу, что эта таблица получена заполнением строка за строкой. Как мы видим g(10,3) <= 934 < 2^10, значит из 10 раундов всегда совершать не более 3 ошибок невозможно, поэтому f(10)<=6. Аналогично f(6)<=3. По этой таблице также видно, что угадать 6 из 9 потенциально возможно, хотя она и не даёт гарантии, что это так. Анонсируя дальнейшие рассуждения скажу, что первое число в этой таблице, которое не соответствует истинному значению g(n,m) - это g(7,2), которое на самом деле не 94, а 93. Это показывает, что эта таблица весьма неплоха, и наши шансы сделать не более 3 ошибок из 9 весьма высоки.
Дальше пойдёт речь о том, как оценить g(n,m) не только сверху, но и снизу, и мы убедимся, что g(9,3)=512, что докажет, что f(9)=6. Такова общая схема решения маленькой задачи для 6 из 9, и начало пути нахождения предела f(n)/n.
Следующий сюжет про то, почему предел f(n)/n < 82%.
Оказывается, это мы можем доказать используя лишь уже полученные средства, а именно первую строку таблицы, слабое неравенство g(n,m) <= g(n-1,m)+3g(n-1,m-1) и тривиальную оценку g(n,m) <= 2^n.
Докажем следующее утверждение (довольно грубое). Если m <= n, то g(n,m) <= 3^m*C_n^m, где C_n^m - число сочетаний из n по m.
Доказательство: докажем индукцией по n. База n=1 очевидна из первой строчки таблицы. Переход: доказано для n-1, докажем для n. Если m < n, то про доказанному неравенству и предположению индукции g(n,m) <= g(n-1,m)+3g(n-1,m-1) <= 3^m * C_(n-1)^m + 3 * 3^(m-1) * C_(n-1)^(m-1) = 3^m * (C_(n-1)^m+C_(n-1)^(m-1)) = 3^m * C_n^m. Иначе, то есть в случае m=n, нам надо доказать, что g(n,n) <= 3^n * 1, что очевидно верно из неравенства g(n,n) <= 2^n. Переход доказан. чтд
Воспользуемся доказанным утверждением для оценки наименьшего m такого, что g(n,m) = 2^n. Попытаемся зафиксировать число t из (0,1) и устремим n к бесконечности, а m будем брать [n * t] так, чтобы оценка из утверждения была асимптотически меньше 2^n. Применим формулу Стирлинга (если не знаете - посмотрите в википедии) для асимптотической оценки (асимптотическую эквивалентность буду обозначать знаком ~) следующего выражения
(C_n^m)^(1/n) = (n!/m!/(n-m)!)^(1/n) ~
~ (n^n/e^n * sqrt(2pi * n) / m^m * e^m / sqrt(2pi*m) / (n-m)^(n-m) * e^(n-m) / sqrt(2pi * (n-m)))^(1/n) ~
~ (n^n / m^m / (n-m)^(n-m))^(1/n) =
= ((1+m/(n-m))^(n-m) * (n/m)^m)^(1/n) =
= (1+m/(n-m)^(1-m/n) * (n/m)^(m/n) ~
~ (1/(1-t))^(1-t) * (1/t)^t. Если мы подберём такое t, что (1/(1-t))^(1-t) * (1/t)^t * 3^t < 2, то оценка из утверждения будет асимптотически меньше 2^n, поэтому g(n, [n*t]) будет меньше 2^n с какого-то момента, значит f(n) будет не больше n-[n*t], а искомый предел f(n)/n будет не больше, чем 1-t. При помощи калькулятора нетрудно убедится, что при t=0.18 выражение (1/(1-t))^(1-t) * (1/t)^t * 3^t принимает значение 1.952.., поэтому предел f(n)/n не больше 82%. На самом деле корень получившегося уравнения равен 0.1892..., поэтому искомый предел f(n)/n не больше 0.8107...
Итого мы доказали обещанную оценку 82% на предел f(n)/n, однако для доказательства утверждения мы использовали слабое неравенство. Я уверен, что использование сильного неравенства должно дать оценку сверху лучше, но мне пока не удалось её получить.
To be continued.
Оно непростое и я в нем еще не разобралась до конца, но собираюсь это сделать. С его разрешения, я копирую его сюда. С удовольствием готова обсуждать частности в комментариях.
Сначала повторю условие.
Алиса и Боб играют против казино. Казино предоставляет произвольную последовательность из 9 нулей и единиц. Боб видит эту последовательность, а Алиса нет. Далее, девять раз повторяется повторяется следующая операция: Алиса говорит 0/1, потом Боб говорит 0/1, потом вскрывается очередная цифра в последовательности, которую предоставило казино. Если все три цифры совпали, то Алиса и Боб выиграли раунд, а иначе проиграли.
Им хочется заранее договориться о стратегии, которая позволит им выиграть хотя бы 6 раундов. Как им это сделать?
Далее будет текст Миши с незначительными поправками. Точнее, его первая часть, в которой мы еще не решим нашу задачу, но немного ее переформулируем и докажем некоторые факты для общего случая.
[Решение]
Будем считать, что раундов всего n (у нас n = 9).
Далее, пусть f(n) - максимальное число раундов из n, которое Алиса с Бобом могут гарантированно угадать (f(9)=6). Тогда я умею доказывать, что существует предел f(n)/n и он лежит между 9/13=0.69.. и 82%.
Итак, теперь о доказательствах и идеях. Начну с доказательства того, что предел f(n)/n есть. Будем доказывать, что эта последовательность стремится к своей верхней грани s. Возьмём любое eps>0. Существует такое n_0, что f(n_0)/n_0 > s - eps/2. Воспользуемся такой стратегией для А. и Б. в произвольном n: разделим все раунды на группы. В первых [n/n_0] группах по n_0 раундов, а в оставшейся n%n_0 раундов. Во всех группах, кроме последней, применим стратегию для n_0, а в последней ходим наобум, то есть ничего не угадываем, нам этого хватит. По такой стратегии мы точно угадаем f(n_0)*[n/n_0] раундов. Понятно, что при такой стратегии доля угаданных будет хотя бы f(n_0) * (n/n_0-1) / n, что стремится к f(n_0)/n_0 при n стремится к бесконечности. Значит с какого-то n_1 доля угаданных больше f(n_0)/n_0-eps/2>s-eps. Мы доказали это для любого eps>0, значит предел f(n)/n равен s. чтд
Теперь покажем простым способом, что этот предел f(n)/n не меньше 2/3. Рассмотрим n вида 3k+1. Разобьём все раунды на группы: первая размера 1, все остальные размера 3. В первом раунде Боб ходит наиболее чаще встречаемом числом из второй группы у казино, а Алиса произвольно. Во второй группе Алиса всегда ходит чаще встречаемым числом, а Боб следующим образом. Если в этой группе у казино 2 числа и одно, то в этих двух числах он ходит ими, а в оставшемся наиболее часто встречающимся у казино в третьей группе. А в случае, если у казино в этой группе 3 одинаковых числа, то в первых двух Боб ходит ими, а в третьем ходит наиболее часто встречающимся из следующей группы. Таким образом Алиса всегда угадает хотя бы 2 из 3 и получит информацию о том, какое число наиболее часто встречаемое в следующей группе. Во всех оставшихся группах повторяем стратегию, как для второй группы, и так гарантированно угадываем 2k из 3k+1.
Таким образом мы получили, что для бесконечной подпоследовательности, а именно n вида 3k+1, искомый предел хотя бы 2/3, а так как у всей последовательности есть предел, то он тоже хотя бы 2/3.
( думаю, если вы получили 5 из 8, то примерно так это и было сделано )
Теперь копнём глубже и переведём задачу на другой язык, который в будущем сможет продемонстрировать в том числе, что 6 из 9 возможно, 7 из 10 невозможно, а искомый предел меньше 82%.
Поставим задачу немного под другим углом: какого наибольшее число g(n,m) строк казино длины n, в которых Алиса и Боб могут так договориться, что точно совершат не более m ошибок из n возможных. Тогда при фиксированном n наименьшее m такое, что g(n,m) = 2^n и будет равно n-f(n). Оценим g(n,m) сверху. В после первого раунда у Алисы будет лишь следующая информация: первое число казино и первый ход Боба. Будем считать, что все игроки ходят детерминировано, потому что для любого вероятностного алгоритма можно взять детерминированный, состоящий из ходов ненулевой вероятности, который будет иметь не меньшее число гарантируемо угадываемых раундов. Таким образом на первом ходу у Алисы не было никакой информации, и она пошла детерминировано, БОО нулём. Далее с точки зрения Алисы все строки казино разбились на 4 группы, которые определяются первыми числами казино и Боба. В трёх из этих групп Алиса ошиблась, а в одной угадала. Внутри каждой группы мы не можем действовать лучше, чем если бы она состояла из каких мы хотим строк длины n-1. Таким образом мы доказали оценку g(n,m)<=g(n-1,m)+3g(n-1,m-1).
Если приглядеться, то это неравенство можно усилить, учтя, что пары групп, соответствующие одинаковым первым раундам казино, в сумме не могут иметь более 2^(n-1) строк казино, потому что именно столько всего строк казино и начинается с одной цифры. Поэтому верно более сильное неравенство:
g(n,m)<=min(g(n-1,m)+g(n-1,m-1), 2^(n-1)) + min(2g(n-1,m-1), 2^(n-1))
Теперь, используя это неравенство, составим таблицу ОЦЕНОК СВЕРХУ на g(n,m), заполняя строки сверху вниз (номер строки n с 1, номер столбца m с 0)
g 0 1 2 3
1 1 2 2 2 ..
2 ? ? ? ?
Надеюсь, содержание первой строки ни у кого вопросов не вызывает. Каждую следующую строку будем заполнять исключительно по предыдущей и доказанному неравенству.
g 0 1 2 3
1 1 2 2 2 ..
2 1 4 4 4 ..
3 1 6 8 8 ..
4 1 9 16 16 ..
5 1 12 32 32 ..
6 1 15 56 64 ..
7 1 18 94 128 ..
8 1 21 148 256 ..
9 1 24 211 512 ..
10 1 27 283 934 ..
..
Поясню например g(3,1). По неравенству оно <= min(4+1, 2^2)+min(1+1,2^2)=4+2=6. Ещё раз скажу, что эта таблица получена заполнением строка за строкой. Как мы видим g(10,3) <= 934 < 2^10, значит из 10 раундов всегда совершать не более 3 ошибок невозможно, поэтому f(10)<=6. Аналогично f(6)<=3. По этой таблице также видно, что угадать 6 из 9 потенциально возможно, хотя она и не даёт гарантии, что это так. Анонсируя дальнейшие рассуждения скажу, что первое число в этой таблице, которое не соответствует истинному значению g(n,m) - это g(7,2), которое на самом деле не 94, а 93. Это показывает, что эта таблица весьма неплоха, и наши шансы сделать не более 3 ошибок из 9 весьма высоки.
Дальше пойдёт речь о том, как оценить g(n,m) не только сверху, но и снизу, и мы убедимся, что g(9,3)=512, что докажет, что f(9)=6. Такова общая схема решения маленькой задачи для 6 из 9, и начало пути нахождения предела f(n)/n.
Следующий сюжет про то, почему предел f(n)/n < 82%.
Оказывается, это мы можем доказать используя лишь уже полученные средства, а именно первую строку таблицы, слабое неравенство g(n,m) <= g(n-1,m)+3g(n-1,m-1) и тривиальную оценку g(n,m) <= 2^n.
Докажем следующее утверждение (довольно грубое). Если m <= n, то g(n,m) <= 3^m*C_n^m, где C_n^m - число сочетаний из n по m.
Доказательство: докажем индукцией по n. База n=1 очевидна из первой строчки таблицы. Переход: доказано для n-1, докажем для n. Если m < n, то про доказанному неравенству и предположению индукции g(n,m) <= g(n-1,m)+3g(n-1,m-1) <= 3^m * C_(n-1)^m + 3 * 3^(m-1) * C_(n-1)^(m-1) = 3^m * (C_(n-1)^m+C_(n-1)^(m-1)) = 3^m * C_n^m. Иначе, то есть в случае m=n, нам надо доказать, что g(n,n) <= 3^n * 1, что очевидно верно из неравенства g(n,n) <= 2^n. Переход доказан. чтд
Воспользуемся доказанным утверждением для оценки наименьшего m такого, что g(n,m) = 2^n. Попытаемся зафиксировать число t из (0,1) и устремим n к бесконечности, а m будем брать [n * t] так, чтобы оценка из утверждения была асимптотически меньше 2^n. Применим формулу Стирлинга (если не знаете - посмотрите в википедии) для асимптотической оценки (асимптотическую эквивалентность буду обозначать знаком ~) следующего выражения
(C_n^m)^(1/n) = (n!/m!/(n-m)!)^(1/n) ~
~ (n^n/e^n * sqrt(2pi * n) / m^m * e^m / sqrt(2pi*m) / (n-m)^(n-m) * e^(n-m) / sqrt(2pi * (n-m)))^(1/n) ~
~ (n^n / m^m / (n-m)^(n-m))^(1/n) =
= ((1+m/(n-m))^(n-m) * (n/m)^m)^(1/n) =
= (1+m/(n-m)^(1-m/n) * (n/m)^(m/n) ~
~ (1/(1-t))^(1-t) * (1/t)^t. Если мы подберём такое t, что (1/(1-t))^(1-t) * (1/t)^t * 3^t < 2, то оценка из утверждения будет асимптотически меньше 2^n, поэтому g(n, [n*t]) будет меньше 2^n с какого-то момента, значит f(n) будет не больше n-[n*t], а искомый предел f(n)/n будет не больше, чем 1-t. При помощи калькулятора нетрудно убедится, что при t=0.18 выражение (1/(1-t))^(1-t) * (1/t)^t * 3^t принимает значение 1.952.., поэтому предел f(n)/n не больше 82%. На самом деле корень получившегося уравнения равен 0.1892..., поэтому искомый предел f(n)/n не больше 0.8107...
Итого мы доказали обещанную оценку 82% на предел f(n)/n, однако для доказательства утверждения мы использовали слабое неравенство. Я уверен, что использование сильного неравенства должно дать оценку сверху лучше, но мне пока не удалось её получить.
To be continued.