19.04 Уменьшение количества камней

Решение руками
Для начала определим значения, из которых Петя выигрывает за один ход. Максимально уменьшить количество камней можно, поделив на , поэтому максимальное значение для победы за один ход равно . Если учитывать округление вниз, числа до также приводят к победе за один ход. Таким образом, при игрок побеждает за один ход. Чтобы Ваня мог выиграть при любом ходе Пети, Петя должен передать Ване выигрышную позицию, то есть все свои ходы должны привести к диапазону . Это возможно при . В ответ записываем минимальное значение , то есть .

Решение программой
Для решения на Python используем рекурсию с проверкой всех возможных ходов, чтобы определить, чья это выигрышная позиция. Функция возвращает , если игра уже завершена (камней ), положительное число – если при оптимальной игре побеждает текущий игрок, и отрицательное – если побеждает соперник. Так как первый ход делает Петя, цикл запускается от его лица: если значение функции положительное, выигрыш принадлежит Пете, а если отрицательное – Ване. При переборе возможных программа находит три числа S, в ответ записываем минимальное

from functools import lru_cache


@lru_cache(None) # Кэширует предыдущие значения функции, что позволяет ускорить работу программы
def game(first_heap):  # Функция игры
    if first_heap <= 21:  # Если камней в куче стало не более 21
        return 0  # Прекращаем игру
    moves = [game(first_heap - 3), game(first_heap - 7), game(first_heap // 4)]  # Прописываем возможные ходы в партии
    win = [i for i in moves if i <= 0]
    if win:  # Проверяем, есть ли выигрыш в данной позиции
        return -max(win) + 1
    else:  # Если в данной позиции выигрыш соперника
        return -max(moves)


for i in range(22, 100):
    if game(i) == -1:  # Если в данной позиции возможен выигрыш Вани первым ходом
        print(i)