Математикадан 53-ші халықаралық олимпиада, 2012 жыл, Мар-дель-Плата

$A$ және $B$ ойыншылары «Өтірікті анықта» деген ойын ойнайды. Бұл ойынның ережесі $k$ және $n$ оң бүтін сандарына байланысты және бұл сандар екі ойыншыға да белгілі.
Ойын басында $A$ ойыншы $x$ және $N$ сандарын $1\le x\le N$ болатындай таңдап алады. $A$ ойыншысы $x$ санын құпияда сақтап, ал $N$ санын $B$ ойыншыға шын айтады. Осыдан кейін $B$ ойыншы $A$ ойыншыға сұрақтар қойып $x$ саны туралы мәлімет алуға тырысады. Сұрақтардың түрлері осындай: әрбір сұрақта $B$ ойыншы өз қалауынша натурал сандардан тұратын $S$ жиынын таңдап (бұл жиын алғашқы сұрақтардың бірінде кездесуі мүмкін), $x$ саны осы жиынға тиісті ме екенін $A$ ойыншыдан сұрайды. $B$ ойыншы қанша сұрақ қойғысы келсе, сонша сұрақ қоя алады. $B$ ойыншының әр сұрағына $A$ ойыншы иә немесе жоқ деп бірден жауап беруге тиіс, бірақ қанша рет болса да өтірік жауап беруіне болады; тек қана бір шектеу бар: кез келген $k+1$ қатар келетін жауаптардың ішінде кемінде бір шын жауап болуы тиіс.
$B$ өзі қажет деп санаған сұрақтар қойғаннан кейін элементтер саны $n$-нен көп емес натурал сандардан тұратын $X$ жиынын көрсетуі тиіс. Егер $x$ ол $X$ жиынына тиісті болса, онда ойыншы $B$ жеңеді; басқа жағдайда $B$ жеңіледі. Дәлелдеңдер:
1. Егер $n\ge {{2}^{k}}$ болса, онда $B$ ойыншының жеңіс стратегиясы бар.
2. Кез келген жеткілікті үлкен $k$ саны үшін, $B$-ның жеңіс стратегиясы жоқ болатындай $n\ge {{1,99}^{k}}$ бүтін саны табылады.

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

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

Доказательство. Сначала Боб задает вопрос 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.

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