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

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

Пример

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

• добавить в кучу два камня;
• добавить в кучу три камня;
• увеличить количество камней в куче в три раза.

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

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

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

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

Решение

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

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

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

from functools import lru_cache


def moves(x):
    return [x + 2, x + 3, x * 3]


def done(x):
    return x >= 106


@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(1, 106)
print(min(s for s in R if any(not done(q) and f(q, 1) for q in moves(s))))

Ответ: 12.

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