Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. Если количество камней в куче делится на целое k (2 ≤ k ≤ 9), то игрок может убрать из кучи k камней. Если количество камней в куче не делится ни на одно из указанных чисел, игрок убирает один камень, после чего выполняет ход по описанному выше правилу.
Например, если в куче 12 камней, то за один ход можно убрать 2, 3, 4 или 6 камней, а если в куче 11 камней, то игрок за один ход сначала убирает один камень (остаётся 10), а затем убирает 2 или 5 камней.
Игра завершается, когда количество камней в куче становится не более 9.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 15 или меньше камней.
В начале игры в куче было S камней, S > 9.
Укажите минимальное значение S, при котором Петя не может выиграть первым ходом, но при любом первом ходе Пети Ваня может выиграть своим первым ходом.
Приведём решение на языке Python.
def Win(m, h):
return 0 if m <= 9 else any([Lose(m-k, h-1) for k in K]) \
if (K:=[i for i in range(2, 10) if not m%i]) else Win(m-1, h-1)
def Lose(m, h):
return 1 if m <= 9 else 0 if not h else all([Win(m-k, h-1) for k in K]) \
if (K:=[i for i in range(2, 10) if not m%i]) else Lose(m-1, h-1)
print('19)', [s for s in range(10, 50) if not Win(s, 1) and Lose(s, 2)][0])
Ответ: 15.