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

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

Пример

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

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

Например, имея кучу из 27 камней, за один ход можно получить кучу из 22 или 9 камней.

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

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

Найдите наименьшее значение S, при котором одновременно выполняются два условия:

• у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
• у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение

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

Проверка для S = 43 (все ходы Пети):

Петя: 38 — одним ходом Ване не выиграть; он ходит в 33, и после любого хода Пети выигрывает своим вторым ходом.
Петя: 14 — Ваня сразу выигрывает ходом в 9.

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

from functools import lru_cache


def moves(x):
    return [x - 5, x // 3]


def done(x):
    return x <= 10


@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(11, 5000)    # верхней границы у S нет — берём с запасом
print(min(s for s in R if f(s, 4) and not f(s, 2)))

Ответ: 43.

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