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

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

Пример

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

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

Например, пусть в одной куче 26 камней, а в другой 41 камень; такую позицию в игре обозначим (26, 41). Тогда за один ход можно получить любую из четырёх позиций: (32, 41), (26, 47), (78, 41), (26, 123).

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

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

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

Решение

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

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

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

from functools import lru_cache


def moves(p):
    a, b = p
    return [(a + 6, b), (a * 3, b), (a, b + 6), (a, b * 3)]


def done(p):
    a, b = p
    return a + b >= 211


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

Ответ: 22.

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