Задание EGEINF687734: Игры и выигрышные стратегии

Решение.
В начале в куче S камней, 1 ≤ S ≤ 66. За ход можно добавить 1 или 4 камня либо увеличить количество камней в 3 раза. Побеждает игрок, первым получивший не менее 67 камней. Петя ходит первым.
Рассматриваем позицию с точки зрения игрока, которому сейчас ходить. Введём четыре класса позиций. W₁ — можно закончить игру следующим ходом. L₁ — любой разрешённый ход передаёт сопернику позицию W₁, поэтому соперник гарантированно выигрывает своим первым ходом.
Для исходной нетерминальной позиции x класс W₁ означает x ≥ 23: это наименьшее число, из которого хотя бы одно разрешённое добавление или умножение достигает 67.
W₂ — выиграть за один ход нельзя, но есть ход в L₁. После такого хода соперник вынужден передать позицию W₁, и игрок завершает игру своим вторым ходом. Проверка здесь состоит из существования одного подходящего собственного хода и проверки всех ответов противника.
L₂ — позиция не относится к L₁, а каждый разрешённый ход ведёт в W₁ или W₂. Тогда соперник гарантирует победу своим первым либо вторым ходом. Исключение L₁ необходимо: по условию задачи 21 победа первым ходом не должна гарантироваться. Терминальную позицию не относим ни к одному из этих четырёх классов: игра в ней уже закончилась.
Нужные начальные значения S — это позиции L₂, поскольку первым ходит Петя, а указанная в условии стратегия нужна Ване. Проверяем допустимые S по возрастанию и выбираем первое подходящее.
Результат последовательной проверки всех начальных S от 1 до 66 включительно по указанным правилам.

Покажем гарантированную стратегию для найденных значений. Каждая строка таблицы — возможное развитие игры; на ходе противника перечислены все допустимые ответы, на ходе победителя выбран один обеспечивающий победу ход. Знак «—» означает, что игра уже закончилась.
При S = 17:

Победу Вани именно первым ходом гарантировать нельзя: Петя может начать переходом в 18. Все возможные ответы Вани из неё: 19, 22, 54. Ни один из них не завершает игру. При этом таблица показывает, как Ваня выигрывает не позднее своего второго хода при любом выборе Пети.
Проверка: все переходы в таблицах разрешены условием, игра нигде не продолжается после достижения порога, а каждая конечная позиция получена ходом нужного игрока. Независимый перебор дерева игры до второго хода каждого игрока подтвердил те же классы для всех проверенных S и все ветви приведённых стратегий.
Следовательно, минимальное подходящее значение S равно 17.
Ответ: 17.