Для игры, описанной в предыдущем задании, найдите такое минимальное значение 
при котором у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход и Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Решение руками
Петя может выиграть своим первым ходом при 
или 
Таким образом, если мы возьмем 
то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.
Но нам то нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем 
чтобы Петя первым ходом удвоил вторую кучу и получил позицию (4, 10). А из этой позиции Ваня уже любым своим ходом создают выигрышную позицию для Пети, после чего Петя выигрывает своим вторым ходом.
Решение БУ
from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap): # Функция игры
if first_heap + second_heap >= 25: # Если камней в куче стало больше 25
return 0 # Прекращаем игру
moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
game(first_heap, second_heap * 2)] # Генерация всех возможных ходов
petya_win = [i for i in moves if i <= 0]
if petya_win:
return -max(petya_win) + 1 # Выигрышный ход Пети
else:
return -max(moves) # Выигрышный ход Вани
# Поиск минимального значения S для выигрыша Пети
for s in range(1, 21):
if game(4, s) == 2:
print(s) # Вывод минимального значения S
break
Решение АР
from functools import lru_cache
def moves(h):
a, b = h
return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)
@lru_cache(None)
def f(h):
if (sum(h) >= 25):
return ’END’
if any(f(x) == ’END’ for x in moves(h)):
return ’P1’
if all(f(x) == ’P1’ for x in moves(h)):
return ’V1’
if any(f(x) == ’V1’ for x in moves(h)):
return ’P2’
for s in range(1, 21):
h = 4, s
if f(h) == ’P2’:
print(s)
break