Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 
камней, за один ход можно получить кучу из 
или 
камней. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 
Если при этом в куче оказалось не более 
камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник на следующем ходе.
В начальный момент в куче было 
камней, 
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите максимальное значение 
при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Решение руками
В данной задаче требуется найти позицию 
. Давайте перед этим найдём позиции 
. Очевидно, что это позиции 
а также позиции 
и 
. Значит нам подойдут значения 
Максимальным из них является 
Решение БУ
from functools import lru_cache
@lru_cache(None)
def game(heap): # Функция игры
# Если кол-во камней в куче стало более 84
if heap > 84:
# Возвращаем 1,
# которая преобразуется в победу Вани первым ходом из-за "плохого" хода Пети
return 1
# Если кол-во камней в куче стало не менее 64
if heap >= 64:
return 0 # Прекращаем игру
# Прописываем возможные ходы в партии
moves = [game(heap + 2), game(heap * 3)]
# Находим значения, через которые может победить Петя
petya_win = [i for i in moves if i <= 0]
if petya_win: # Если такие значения нашлись и список не пуст
return -max(petya_win) + 1
else: # Иначе побеждает Ваня максимальным ходом
return -max(moves)
for S in range(1, 63 + 1): # Перебор значений S
if game(S) == -1: # Гарантированная победа Пети третьим ходом
print(S) # В ответ берём последнее выведенное значение