Петя и Ваня ходят по очереди. Начинает Петя. За ход можно убрать 5 камней из первой кучи, убрать 3 из второй, разделить первую кучу на 2 с округлением вниз или разделить вторую на 2 с округлением вверх.
Игра заканчивается, когда в двух кучах суммарно не больше 60 камней. Побеждает сделавший последний ход. В первой куче изначально 130 камней, во второй — , где .
Найдите два наименьших значения , при которых Петя не может выиграть первым ходом, но гарантирует победу вторым. Запишите значения по возрастанию.
Решение:
Первую кучу делим через k1 // 2, вторую — через ceil(k2 / 2). В hod включаем только разрешённые ходы. Проверяем победу Пети за три общих хода и исключаем победу первым.
from math import ceil
def F(k1, k2, x):
if k1 + k2 <= 60:
return x % 2 == 0
if x == 0:
return 0
hod = []
if k1 >= 5:
hod.append(F(k1 - 5, k2, x - 1))
if k2 >= 3:
hod.append(F(k1, k2 - 3, x - 1))
if k1 > 0:
hod.append(F(k1 // 2, k2, x - 1))
if k2 > 1:
hod.append(F(k1, ceil(k2 / 2), x - 1))
return any(hod) if x % 2 != 0 else all(hod)
values = [k for k in range(5, 151)
if not F(130, k, 1) and F(130, k, 3)]
print(*values[:2])
Ответ — 29 30.
Ответ: