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

Решение руками
Из предыдущих заданий известно, что Петя гарантированно побеждает своим вторым ходом из позиций

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

Проверим подряд кандидаты, начиная с .

• : после ходов Пети получаем – все в , значит Ваня выигрывает сразу первым ходом при любых ходах Пети, поэтому не подходит (нужна ситуация, когда Ваня не гарантированно выигрывает первым ходом).
• : после ходов Пети получаем – опять все в , поэтому не подходит.
• : после ходов Пети получаем – опять все в , не подходит.
• : после ходов Пети получаем . Здесь и , значит для хода Пети в Ваня не получает гарантированного выигрыша за 1 или 2 хода, поэтому не подходит.
• аналогично дают одно из образовавшихся значений вне множества выигрышных позиций, поэтому тоже не подходят.

• : после ходов Пети получаем

  

  Все три результата принадлежат либо множеству позиций «выигрыш за 1 ход» (), либо множеству позиций «выигрыш за 2 хода» (). Значит при любом ходе Пети Ваня имеет выигрышную стратегию, позволяющую ему выиграть первым или вторым ходом, и при этом не во всех ветках у Вани есть мгновенная победа за 1 ход (поскольку для хода Пети, давшего , Ваня выигрывает вторым ходом).

Следовательно, минимальное значение , удовлетворяющее требованиям, равно

Решение программой
Этот код почти идентичен реализации из задачи 19, а единственное отличие заключается в условии проверки в цикле: здесь проверяется game(S) == -2, что соответствует поиску начальных значений , из которых Ваня выигрывает первым или вторым ходом.

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, 1000):
    if game(i) == -2:  # Если в данной позиции возможен выигрыш Вани за один или два хода
        print(i)