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

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

Пример

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

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

Например, пусть в одной куче 75 камней, а в другой 84 камня; такую позицию в игре обозначим (75, 84). Тогда за один ход можно получить любую из четырёх позиций: (73, 84), (75, 82), (25, 84), (75, 28).

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

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

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

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

Решение

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

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

Петя: (64, 66) — одним ходом Ване не выиграть; он ходит в (64, 64), и после любого хода Пети выигрывает своим вторым ходом.
Петя: (22, 66) — Ваня сразу выигрывает ходом в (7, 66);
Петя: (66, 64) — одним ходом Ване не выиграть; он ходит в (64, 64), и после любого хода Пети выигрывает своим вторым ходом.
Петя: (66, 22) — Ваня сразу выигрывает ходом в (22, 22).

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

from functools import lru_cache


def moves(p):
    a, b = p
    return [(a - 2, b), (a // 3, b), (a, b - 2), (a, b // 3)]


def done(p):
    a, b = p
    return a + b <= 84


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

Ответ: 66.

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