Задание №20. Победа Пети вторым ходом

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

Что требуется от первого хода

Позиция — состояние игры перед ходом; для одной кучи это число камней. Позиция оценивается относительно игрока, который сейчас ходит. Петя начинает, затем ходит Ваня, затем снова Петя. Второй собственный ход Пети — третий ход в этой общей последовательности.

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

Полный пример: уменьшение кучи

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

1. Где возможна немедленная победа

Из текущего числа s доступны s-3, s-5 и \lfloor s/4\rfloor. Знак \lfloor\ \rfloor обозначает округление вниз. Деление заканчивает игру, когда частное меньше 11: s<44. Вычитания позволяют победить лишь до 13 и 15 соответственно, поэтому более широкого диапазона не добавляют.

Итак, из любого целого числа от 11 до 43 ходящий сразу побеждает. Эти позиции обозначим W_1 — «победа за один собственный ход». Начальные S\le43 не подходят: возможность первого выигрыша Пети запрещена условием.

2. Что нужно оставить Ване

Далее рассматриваются 44, 45 и 46. Из них ни один ход не оставляет десять камней или меньше, зато каждый результат попадает в диапазон W_1.

Игрок, получивший одну из этих трёх позиций, вынужден дать сопернику победу за ход. Такие позиции обозначим L_1 — «соперник гарантированно выигрывает следующим ходом». Для Пети это подходящая цель первого действия: если передать Ване 44, 45 или 46, любой его ответ вернёт Пете W_1.

3. Первое подходящее значение

При S=47 Петя убирает три камня: 47\to44. Теперь ход Вани. Он может убрать три, убрать пять или разделить на четыре. Таблица сохраняет все его ответы и показывает по одному завершающему действию Пети.

Первый ход Пети и любой ответ Вани оставляют более десяти камней. Значит, очередь второго хода Пети действительно наступает, и во всех трёх ветвях он заканчивает игру. Из 47 немедленной победы нет, поэтому выполнены оба требования.

4. Второе значение и проверка минимальности

При S=48 Петя также убирает три: 48\to45. Правила прежние: вычесть три, вычесть пять или разделить на четыре вниз; победа при результате не более десяти.

При начальных значениях от 11 до 43 Петя уже может выиграть первым ходом. При 44, 45 и 46, как показала таблица, после любого его хода сразу выигрывает Ваня. Все меньшие значения исключены, а 47 и 48 подходят. Ответ: 47 48.

Это два наименьших значения, а не полный список. Например, 49 тоже подходит: Петя передаёт 46, а после любого ответа Вани получает победу за ход. Формат ответа определяется вопросом задачи.

Та же стратегия в растущей игре

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

Немедленная победа возможна из 23–66. Из 22 любой ход даёт 23, 26 или 66, поэтому 22 выгодно передать противнику. Других таких позиций нет: при числе не больше 21 можно прибавить один и оставить меньше 23. Петя может передать 22 из 18 прибавлением четырёх или из 21 прибавлением единицы. После ответов Вани 23, 26 и 66 Петя завершает игру соответственно утроением, утроением и прибавлением единицы. Ответ: 18 21.

Если куч две

В задаче о втором ходе при двух кучах ↗ используются правила игры до суммы 154 ↗. Начало — (11,S), 1\le S\le142; за ход прибавляют четыре в одну кучу или утраивают одну кучу. Победу даёт общая сумма не меньше 154.

Из пары (a,b) проверяются четыре выхода: (a+4,b), (3a,b), (a,b+4), (a,3b). На своём первом ходе Петя выбирает один из них; у Вани учитываются все четыре ответа. Пара сохраняется целиком: одной суммы недостаточно, чтобы вычислить результат утроения выбранной кучи. Логика выбора и гарантии при этом не меняется.

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

• Один удобный ответ Вани. В убывающей игре ↗ цепочка 47\to44\to41\to10 описывает лишь одну партию. Гарантию дают также проверенные ответы через 39 и 11. На ходе противника сохраняются все разрешённые варианты.
• Все первые ходы Пети вместо одного. Из 48 ход 48\to43 позволяет Ване победить сразу. Это не отменяет стратегию через 45: Петя сам выбирает первый ход. Проверка всех его первых действий отвергла бы верное значение.
• Пропуск раннего окончания. В той же игре после 48\to43\to10 победил Ваня. Продолжать до второго хода Пети нельзя. Условие окончания проверяется перед построением следующих ветвей.
• Второй общий ход вместо второго собственного. В растущей игре ↗ последовательность 18\to22\to23\to69 содержит три действия: Петя, Ваня, Петя. Если считать второй стрелкой победу Пети, роли игроков перепутаются. Рядом со слоями указываются имена.
• Принять любой найденный успех за ответ. В задаче о двух наименьших значениях ↗ 43 исключается возможностью первого выигрыша, а 49 не входит в ответ из-за меньших подходящих 47 и 48. Проверяются оба условия и требуемый порядок отбора.