Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча молитв. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу одну или три молитвы или увеличить количество молитв в куче в 
раза, при этом после каждого хода в куче должно быть нечетное количество молитв. Например, пусть в куче будет 
молитв. Тогда за один ход можно получить кучу из 
или 
молитв. Игра завершается в тот момент, когда количество молитв в куче становится не менее 
.
Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет 
или более молитв. В начальный момент в куче было 
молитв; 
.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите минимальное значение 
, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Решение руками
Для начала нужно определить в каких ситуациях какие ходы мы можем совершать. Мы знаем, что после хода должно быть обязательно нечётное количество камней в куче. Если значение камней в куче это чётное число, то тогда мы можем совершить только 
,
ходы, так как чётное + нечётное = нечётное число. В обратном случае, если значение камней в куче это нечётное число, то тогда мы можем совершить только 
ход, так как нечётное * нечётное = нечётное число. Теперь определим при каких значениях Петя побеждает своим первым ходом. Максимальный ход, который мы имеем в партии это 
ход. Значит, минимальное значение, при котором Петя побеждает своим первым ходом равняется: 
.
Поскольку это значение нечётное, то оно подходит. Получается, нам подходят все нечётные значения от 
до 
и также 
и 
, так как из этих значений можно дойти до 
камней ходом 
. Теперь определелим значение, при котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанные значения – это значение, в котором Ваня выигрывает своим первым ходом. Распишем минимальное значение S, при котором Ваня побеждает первым ходом:
. Петя может только увеличить количество камней до 
. Ване не составит труда завершить партию следующим ходом.
Ответ: 
Решение БУ
from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
if first_heap >= 51: # если камней в куче стало больше 50
return 0 # прекращаем игру
moves = [] # cписок всех возможных ходов в партии
if first_heap % 2 == 0: # если количество камней в куче является чётным
# то можем совершить только +1, +3 ходы, так как чётное+нечётное = нечётное
moves = [game(first_heap+1),game(first_heap+3)]
else: # если количество камней в куче является нечётным
# то можем совершить только *3 ход, так как нечётное*нечётное = нечётное
moves = [game(first_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 i in range(1,51):
# если в данной позиции возможен выигрыш Вани первым ходом
if game(i) == -1:
print(i)
break
Решение АР
from functools import lru_cache
def moves(heap):
m = []
if (heap * 3) % 2 != 0:
m += [heap * 3]
if (heap + 1) % 2 != 0:
m += [heap + 1]
if (heap + 3) % 2 != 0:
m += [heap + 3]
return m
@lru_cache(None)
def game(heap):
if heap >= 51:
return ’END’
elif any(game(x) == ’END’ for x in moves(heap)):
return ’WIN1’
elif all(game(x) == ’WIN1’ for x in moves(heap)):
return ’LOSE1’
elif any(game(x) == ’LOSE1’ for x in moves(heap)):
return ’WIN2’
elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
return ’LOSE2’
for s in range(1, 51):
if game(s) == ’LOSE1’:
print(s)
break