Петя и Ваня по очереди ходят в игре с одной кучей. Начинает Петя. За ход можно выполнить одно действие:
- убрать 5 камней;
- разделить количество камней на 2, если оно чётное;
- разделить количество камней на 3, если оно кратно 3;
- прибавить 1, если число камней нечётное и не кратно 3.
Например, из 12 можно получить 7, 6 или 4, а из 11 — 6 или 12. Побеждает тот, после чьего хода в куче не больше 19 камней. Изначально в ней камней, .
Найдите минимальное , при котором Петя не может выиграть за один ход, а Ваня может выиграть своим первым ходом после любого хода Пети.
Решение:
В hod добавляем только доступные ходы. Из числа, кратного 6, разрешены оба деления. Проверяем F(k, 2): после любого хода Пети у Вани должен быть выигрышный ответ.
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 F(k, 2)]
print(values[0])
Ответ — 25.
Ответ:
25