Задание 19 ЕГЭ: одна куча, камни убираются

Одна куча, камни убираются: Ваня выигрывает первым ходом. Тема номера — теория игр, выигрыш первым ходом. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

• убрать из кучи четыре камня;
• убрать из кучи шесть камней;
• уменьшить количество камней в куче в четыре раза (количество камней, полученное при делении, округляется до меньшего).

Например, имея кучу из 58 камней, за один ход можно получить кучу из 54, 52 или 14 камней.

Игра завершается в тот момент, когда количество камней в куче становится не более 20. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в куче будет 20 или меньше камней. В начальный момент в куче было S камней; S > 20.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Решение

Нужны S, при которых Петя не выигрывает первым ходом, а после любого его хода у Вани есть ход, заканчивающий игру. В программе это f(S, 2): «наш» игрок — Ваня, за два полухода (ход Пети и ответ Вани) он выигрывает при любом ходе Пети.

Проверка для S = 84: после каждого хода Пети у Вани есть ход, заканчивающий игру (Петя → Ваня):

84 → 80 → 20
84 → 78 → 19
84 → 21 → 17

Программа: f(p, m) — может ли «наш» игрок выиграть из позиции p не более чем за m полуходов (на нечётном m ходит «наш» игрок — нужен хотя бы один хороший ход, any; на чётном ходит соперник — хорошими должны быть все его ходы, all).

from functools import lru_cache


def moves(x):
    return [x - 4, x - 6, x // 4]


def done(x):
    return x <= 20


@lru_cache(None)
def f(p, m):
    if done(p):
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(q, m - 1) for q in moves(p)]
    return any(h) if m % 2 else all(h)


R = range(21, 1000)    # верхней границы у S нет — берём с запасом
print(min(s for s in R if f(s, 2)))

Ответ: 84.

Решить такую задачу — новый вариант с проверкой