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

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

Пример

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

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

Например, пусть в одной куче 72 камня, а в другой 91 камень; такую позицию в игре обозначим (72, 91). Тогда за один ход можно получить любую из четырёх позиций: (71, 91), (72, 90), (36, 91), (72, 45).

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

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

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

Решение

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

Проверка для S = 41: Петя ходит (68, 41) → (67, 41) (игра не закончилась), Ваня отвечает ходом в (66, 41) и выигрывает.

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

from functools import lru_cache


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


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


@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(40, 500)    # верхней границы у S нет — берём с запасом
print(min(s for s in R if any(not done(q) and f(q, 1) for q in moves((68, s)))))

Ответ: 41.

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