Петя и Ваня по очереди меняют число камней в куче. Первым ходит Петя. Можно прибавить камень или удвоить число камней. Игра заканчивается при 21 камне или больше. Побеждает сделавший последний ход. В начале в куче камней, .
Найдите два наименьших значения , при которых Петя гарантирует победу не позднее третьего своего хода, но не может гарантировать её первым или вторым ходом. Запишите значения по возрастанию.
Решение:
Условие остановки — k >= 21. В hod два хода: прибавить камень и удвоить кучу. Третий ход Пети — пятый ход партии. F(k, 3) учитывает победу и первым, и вторым ходом Пети, поэтому одного исключения not F(k, 3) достаточно.
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, 3) and F(k, 5)]
print(*values[:2])
Ответ — 4 7.
Ответ: