20.01 Теория игр

Решение руками

Из предыдущей задачи мы знаем, что в отрезке [61;70] Петя гарантированно выигрывает своим первым ходом. В значении 60 Ваня гарантированно выигрывает своим первым ходом после любого хода Пети. Значит, что если после первого хода Пети в куче станет 60 камней, значит, он гарантированно выиграет в партии своим вторым ходом. Распишем из каких значений за один ход можно попасть в 60:

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

Если , то Пете достаточно прибавить к куче камней. Далее аналогично предыдущим действиям.

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 71: # если камней в куче стало больше 70
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+10)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,71):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)