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

Решение.
В начале в куче S камней, S ≥ 17. За ход можно убрать 3 или 8 камней либо уменьшить число камней в 3 раза с округлением вниз. Игра заканчивается при количестве не больше 16; победитель — сделавший последний ход. Петя начинает.
Например, результат деления x на 3 — целая часть дроби x3. Округление вверх и обычное дробное значение не соответствуют правилам.
Рассматриваем позицию с точки зрения игрока, которому сейчас ходить. Введём четыре класса позиций. W₁ — можно закончить игру следующим ходом. L₁ — любой разрешённый ход передаёт сопернику позицию W₁, поэтому соперник гарантированно выигрывает своим первым ходом.
Для исходной нетерминальной позиции x класс W₁ означает x ≤ 50. Действительно, после вычитания нужно x ≤ 24, а после деления с округлением вниз — x < 51, то есть x ≤ 50. Объединяем эти два условия.
W₂ — выиграть за один ход нельзя, но есть ход в L₁. После такого хода соперник вынужден передать позицию W₁, и игрок завершает игру своим вторым ходом. Проверка здесь состоит из существования одного подходящего собственного хода и проверки всех ответов противника.
L₂ — позиция не относится к L₁, а каждый разрешённый ход ведёт в W₁ или W₂. Тогда соперник гарантирует победу своим первым либо вторым ходом. Исключение L₁ необходимо: по условию задачи 21 победа первым ходом не должна гарантироваться. Терминальную позицию не относим ни к одному из этих четырёх классов: игра в ней уже закончилась.
Нужные начальные значения S — это позиции W₂. Проверяем допустимые S в порядке возрастания и выбираем первые два подходящих значения.
Результат последовательной проверки всех начальных S от 17 до 55 включительно по указанным правилам.

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

Первым ходом Петя может получить 51, 46, 18. Ни одна из этих позиций не завершает игру. Показанный в таблице первый ход оставляет сопернику позицию L₁, а затем при каждом ответе соперника Петя достигает порога своим вторым ходом.
При S = 55:

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