53-я Международная Математическая OлимпиадаАргентина, Мар-дель-Плата, 2012 год

Два игрока $A$ и $B$ играют в игру Угадай-ка. Правила этой игры зависят от двух положительных целых чисел $k$ и $n$, и эти числа известны обоим игрокам. В начале игры $A$ выбирает целые числа $x$ и $N$ такие, что $1\le x\le N$. Игрок $A$ держит число $x$ в секрете, а число $N$ честно сообщает игроку $B$. После этого игрок $B$ пытается получить информацию о числе $x$, задавая игроку $A$ вопросы следующего типа: за один вопрос $B$ указывает по своему усмотрению множество $S$, состоящее из целых положительных чисел (возможно, это множество уже было указано в одном из предыдущих вопросов) и спрашивает игрока $A$ принадлежит ли число $x$ множеству $S$. Игрок $B$ может задать столько вопросов, сколько он хочет. На каждый вопрос игрока $B$ игрок $A$ должен сразу ответить да или нет, при этом ему разрешается соврать столько раз, сколько он хочет; единственное ограничение состоит в том, что из любых $k+1$ подряд идущих ответов хотя бы один ответ должен быть правдивым.
После того, как $B$ задаст столько вопросов, сколько он сочтет нужным, он должен указать множество $X$, содержащее не более $n$ целых положительных чисел. Если $x$принадлежит множеству $X$, то игрок $B$ выиграл; иначе $B$ проиграл. Докажите, что:
1. Если $n\ge {{2}^{k}}$, то $B$ может гарантировать себе выигрыш.
2. Для всякого достаточно большого $k$ найдется целое число $n\ge {{1,99}^{k}}$, при котором игрок $B$ не сможет гарантировать себе выигрыш.

Комментарий/решение

Часть (а): Докажем следующее.

Доказательство. Сначала Боб задает вопрос S0 = {2k + 1}, пока Алиса не ответит «да» или пока Боб не задаст k + 1 вопросов. Если Алиса ответит «нет» на все эти вопросы, то Боб исключает 2k + 1. Итак, предположим, что Алиса только что сказала «да».

Пусть теперь T = {1,...,2k}. Затем он задает k-последующие вопросы S1, ..., Sk, определяемые следующим образом:

• S1 = {1,3,5,7,...,2k −1} состоит из всех чисел из T, младшая цифра которых в двоичном формате равна 1.

• S2 = {2, 3, 6, 7, . . . , 2k − 2, 2k − 1} состоит из всех чисел из T, вторая младшая цифра которых в двоичном формате равна 1.

• В более общем смысле Si состоит из всех чисел из T, у которых i-я младшая цифра в двоичном формате равна 1.

WLOG Алиса на все вопросы отвечает «да» (остальные случаи аналогичны). Среди последних k + 1 ответов хотя бы один должен быть правдивым, а число 2k (имеющее нули во всех соответствующих цифрах) не встречается ни в одном из S0, . . . , Sk и исключено.

Таким образом, таким образом Боб может неоднократно находить невозможные варианты для x (а затем переименовывать оставшихся кандидатов на 1,..., N − 1), пока не придет к набору, состоящему не более чем из 2k чисел.

Часть (b): Достаточно рассмотреть n = 1,99k и N = n + 1 для больших k. На t-м шаге Боб задает вопрос St; мы формулируем каждый из ответов Алисы в виде «x ∈/ Bt», где Bt — это либо St, либо его дополнение. (Вы можете думать об этом как о «плохих наборах»; идея состоит в том, чтобы показать, что мы можем избежать появления какого-либо числа в k + 1 последовательных плохих наборах, не позволяя Бобу исключать какие-либо числа.)

Основная идея: для каждого числа 1 ≤ x ≤ N на временном шаге t мы определяем его вес как w(x) = 1,998e.

где e — наибольшее число такое, что x ∈ Bt−1 ∩ Bt−2 ∩ · · · ∩ Bt−e.

Утверждение — Алиса может гарантировать, что общий вес никогда не превысит 1,998k+1 для больших k.

Доказательство. Обозначим через Wt сумму весов после t-го вопроса. Имеем W0 = N < 1000n. Индуктивно докажем, что Wt < 1000n всегда.

В момент времени t Боб задает вопрос St. Мы предлагаем Алисе выбрать Bt в зависимости от того, какой из St или St имеет меньший общий вес, следовательно, не более Wt/2. Веса для Bt увеличиваются в 1,998 раза, а все веса для Bt сбрасываются до 1. Таким образом, новый общий вес после времени t равен W ≤1,998·Wt/2 ≤0,999W +n. т+1 2 т т

Таким образом, если Wt < 1000n, то Wt+1 < 1000n.

В заключение отметим, что 1000n < 1000 1,99k + 1 < 1,998k+1 для большого k.

В частности, ни одно отдельное число не может иметь вес 1,998k+1. Таким образом, для каждого временного шага t мы имеем

Bt ∩Bt+1 ∩···∩Bt+k =∅.

Затем, как только Боб остановится, если он объявит набор из n положительных целых чисел, а x — это целое число, которое Боб не выбрал, тогда история вопросов Алисы согласуется с тем, что x — это число Алисы, так как среди любых k + 1 последовательных ответов, которые она утверждала, x ∈ Но для некоторого t в этом диапазоне.

Замечание (Мотивация). В нашей настройке Bt давайте подумаем задом наперед. Проблема эквивалентна предотвращению e = k + 1 на любом временном шаге t для любого числа x. Это значит

• иметь не более двух элементов с = kattimet-1,

• таким образом иметь не более четырех элементов с e=k-1 attimet-2, • таким образом иметь не более восьми элементов с e=k-2 attimet-3, • и так далее.

Мы уже использовали это при решении части (а). В любом случае теперь вполне естественно попытаться положить w(x) = 2e, так что все вышеперечисленные случаи в сумме приведут к «одинаково плохим» ситуациям: скажем, поскольку 8 · 2k−2 = 4·2k−1 =2·2k.

Однако тогда мы получаем Wt+1 ≤ 12 (2Wt) + n, которое может неограниченно увеличиваться за счет вклада чисел, обнуляющихся. Чтобы исправить это, нужно изменить вес на w(x) = 1,998e, воспользовавшись тем небольшим дополнительным пространством, которое у нас есть из-за n ≥ 1,99k, а не n ≥ 2k.

Отличное решение