Петя и Ваня по очереди меняют число камней в куче. Первым ходит Петя. Можно прибавить камень или удвоить число камней. Игра заканчивается при 21 камне или больше. Побеждает сделавший последний ход. В начале в куче камней, .
Найдите минимальное , при котором Петя не может выиграть за один ход, но гарантирует победу своим вторым ходом.
Решение:
Условие остановки — k >= 21. В hod два хода: прибавить камень и удвоить кучу. Проверяем победу Пети за три общих хода и исключаем победу первым.
def F(k, x):
if k >= 21:
return x % 2 == 0
if x == 0:
return 0
hod = [F(k + 1, x - 1), F(k * 2, x - 1)]
return any(hod) if x % 2 != 0 else all(hod)
values = [k for k in range(1, 21)
if not F(k, 1) and F(k, 3)]
print(values[0])
Ответ — 5.
Ответ:
5