Задание №19. Первый ход: возможность и гарантированная победа

В игре заданы начальное количество камней, разрешённые действия и условие окончания. Требуется найти начальное значение, при котором один из игроков сможет победить указанным ходом. Основа решения — сначала определить, из каких позиций можно закончить игру сразу, а затем связать с ними первые ходы Пети. При этом «после неудачного хода» и «после любого хода» требуют разных проверок.

Что считается позицией и победой

Позиция описывает состояние игры перед очередным ходом. Для одной кучи достаточно числа камней; для двух нужны оба числа. Рядом с позицией важно знать, кто ходит сейчас. Петя начинает, далее игроки чередуются.

После каждого хода проверяется условие окончания. Если оно выполнено, игра уже закончилась и ответного хода нет. Такая позиция называется терминальной. Позиция, из которой ходящий игрок может сразу закончить игру своей победой, сама ещё не терминальна: завершающий ход только предстоит.

Полный пример: победа Вани после любого хода

В игре с уменьшением кучи ↗ первоначально S\ge11 камней. За ход можно убрать три камня, убрать пять или разделить число камней на четыре с округлением вниз. Игра заканчивается, когда остаётся не более десяти камней; выигрывает сделавший последний ход. Требуется наименьшее S, при котором Петя не может выиграть первым ходом, а Ваня после любого первого хода Пети может выиграть своим первым.

Разрешённые переходы из текущего числа s: s-3, s-5, \lfloor s/4\rfloor. Скобки \lfloor\ \rfloor означают округление вниз: например, \lfloor43/4\rfloor=10.

1. Позиции с немедленной победой

Сначала рассматривается игрок, которому сейчас принадлежит ход. Убрав три камня, он выигрывает при s\le13; убрав пять — при s\le15. Деление позволяет выиграть из большего диапазона. Чтобы после округления получилось не более десяти, частное должно быть меньше одиннадцати:

\lfloor s/4\rfloor\le10 равносильно s<44.

Камни считаются целыми числами, а при десяти и меньше игра уже окончена. Поэтому все ещё продолжающиеся позиции с победой за один ход — 11\le s\le43. Вычитания этот диапазон не расширяют. При S\le43 Петя сразу делит кучу и выигрывает; такие начальные значения не удовлетворяют вопросу.

2. Все первые ходы из следующего значения

Первое оставшееся значение — S=44. Ни одно действие Пети не заканчивает игру: получаются 41, 39 или 11 камней. Все три числа лежат в найденном диапазоне от 11 до 43. Теперь для каждого результата нужен завершающий ответ Вани.

В каждой строке ответ Вани оставляет не более десяти камней. Ему не требуется заранее выбирать одну операцию на все случаи: ответ выбирается после хода Пети. Такая возможность победить независимо от выбора соперника и есть гарантия победы.

3. Проверка минимальности

При всех допустимых S от 11 до 43 Петя может закончить игру первым ходом. Значение 44 удовлетворяет обоим требованиям: Петя сразу не выигрывает, а все его выходы допускают победу Вани. Следовательно, меньше подходящего значения нет. Ответ: 44.

Когда куча растёт

В игре с прибавлением и утроением ↗ ход добавляет один камень, добавляет четыре или утраивает кучу. Начальная куча содержит от 1 до 66 камней; победа наступает при 67 или более. Вопрос тот же: Петя не выигрывает сразу, Ваня выигрывает после любого его хода.

Утроение даёт немедленную победу начиная с 23: 3\cdot23=69\ge67. Прибавления не дают новых выигрышных позиций ниже этой границы. Из 22 Петя получает 23, 26 или 66; Ваня завершает игру соответственно утроением, утроением или прибавлением единицы. При S\le21 Петя может прибавить один и передать не более 22 камней, откуда Ваня сразу не выигрывает. При S\ge23 уже выигрывает Петя. Поэтому ответ — 22. Направление числовой границы изменилось, проверка всех ходов осталась прежней.

Когда достаточно одного неудачного хода

В игре с двумя кучами и неудачным ходом Пети ↗ начальная позиция — (11,S), где 1\le S\le142. За ход можно добавить четыре камня в одну кучу или утроить одну кучу. Победа наступает при общей сумме не менее 154. Требуется минимальное S, при котором Ваня может выиграть первым ходом после неудачного хода Пети.

Здесь достаточно одной допустимой последовательности из двух ходов. При S=16 Петя утраивает вторую кучу, затем Ваня делает то же:

(11,16)\to(11,48)\to(11,144).

После Пети сумма равна 59: игра продолжается. После Вани сумма равна 155: он выиграл. Это и есть нужная неудачная ветвь Пети. Требовать проигрыша после каждого его хода здесь не нужно.

Для доказательства минимума рассматриваются все S\le15. При таком ограничении начальная позиция не превосходит (11,15) по каждой куче. Прибавление и утроение сохраняют этот порядок, поэтому достаточно верхней оценки для этой пары. В обеих её кучах утроение даёт больше камней, чем прибавление четырёх; после первого хода это остаётся верным. Наибольшая сумма за два хода достигается двумя утроениями. Возможны три распределения этих действий:

Все суммы меньше 154. Значит, при меньшем S даже два наиболее выгодных для роста хода не дают победы. Ответ: 16.

Возможные ловушки

• Одна ветвь вместо слова «любой». В игре с уменьшением ↗ цепочка через 41 проверяет лишь вычитание трёх. Пропуск деления может скрыть возможность спасения Пети. Полная проверка содержит все три результата его хода.
• Все ходы вместо одного неудачного. В игре с двумя кучами ↗ требование проигрыша Пети при любом ходе усиливает условие и может исключить правильный ответ. Для возможности после ошибки достаточно одной незавершающей ветви Пети и выигрышного ответа Вани.
• Округление к ближайшему целому. В убывающей игре ↗ замена \lfloor43/4\rfloor=10 на 11 неверно уберёт 43 из позиций немедленной победы. Проверяется именно целая часть частного, то есть округление вниз.
• Продолжение после победы. В той же игре после 41\to10 Ваня уже победил. Следующая стрелка приписала бы ход игроку, очередь которого не наступает. После каждой операции сначала проверяется порог.
• Изменение обеих куч или порога. В двухкучевом примере ↗ переход (11,16)\to(33,48) требует двух действий и не является одним ходом. А позиция (11,144) уже завершает игру по сумме, хотя ни одна куча не достигла 154. Проверяются одна выбранная куча и сумма обеих.