Петя и Ваня по очереди ходят в игре с одной кучей. Начинает Петя. За ход можно выполнить одно действие:
- убрать 5 камней;
- разделить количество камней на 2, если оно чётное;
- разделить количество камней на 3, если оно кратно 3;
- прибавить 1, если число камней нечётное и не кратно 3.
Например, из 12 можно получить 7, 6 или 4, а из 11 — 6 или 12. Побеждает тот, после чьего хода в куче не больше 19 камней. Изначально в ней камней, .
Найдите минимальное , при котором Ваня гарантирует победу первым или вторым ходом, но не может гарантировать победу первым ходом.
Решение:
В hod добавляем только доступные ходы. Из числа, кратного 6, разрешены оба деления. Проверяем победу Вани не позднее четвёртого общего хода и исключаем гарантированную победу за два общих хода.
def F(k, x):
if k <= 19:
return x % 2 == 0
if x == 0:
return 0
hod = [F(k - 5, x - 1)]
if k % 2 == 0:
hod.append(F(k // 2, x - 1))
if k % 3 == 0:
hod.append(F(k // 3, x - 1))
if k % 2 != 0 and k % 3 != 0:
hod.append(F(k + 1, x - 1))
return any(hod) if x % 2 != 0 else all(hod)
values = [k for k in range(20, 1540)
if not F(k, 2) and F(k, 4)]
print(values[0])
Ответ — 60.
Ответ:
60