Для игры, описанной в задании 4, найдите разность максимального и минимального значения S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым, вторым или третьим ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым или вторым ходом.
Решение руками
Если третий ход Пети приведет его в область проигрыша, значит, в этой позиции Ваня победит в игре третьим ходом. Минимальное значение, при котором возможна такая ситуация равняется 
.Развитие партии будет таково: Максимальное значение, при котором возможна такая ситуация будет равным
.Развитие партии будет таково:
Решение программой
from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
if first_heap >= 40: # если камней в куче стало больше 39
return 0 # прекращаем игру
if first_heap % 6 == 0: # если текущее количество камней кратно 6
moves = [game(first_heap*2),game(first_heap*3),game(first_heap+3)] # то мы можем совершить любой ход
else: # в ином случае
moves = [game(first_heap + 3)] # мы можем совершить только ход +3
petya_win = [i for i in moves if i <= 0]
if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
return -max(petya_win) + 1
else: # если в данной позиции выигрыш Вани
return -max(moves)
ans = []
for i in range(1,40):
if game(i) == -3: # если в данной позиции возможен выигрыш Вани третьим ходом
ans += [i]
print(max(ans)-min(ans))