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

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

Пример

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

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

Например, пусть в одной куче 62 камня, а в другой 70 камней; такую позицию в игре обозначим (62, 70). Тогда за один ход можно получить любую из четырёх позиций: (60, 70), (62, 68), (20, 70), (62, 23).

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

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

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

• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания через пробел.

Решение

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

Подходят S = 52, 53, 153, 154, 155. Нужны два наименьших из них.

Проверка для S = 52: выиграть первым ходом Петя не может, а ходом (69, 52) → (67, 52) он ставит Ваню в проигрышную позицию: любой ход Вани (слева) Петя заканчивает выигрышным ходом (справа):

(65, 52) → (21, 52)
(22, 52) → (20, 52)
(67, 50) → (22, 50)
(67, 17) → (22, 17)

Программа: 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 <= 73


@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(5, 5000)    # верхней границы у S нет — берём с запасом
a20 = [s for s in R if f((69, s), 3) and not f((69, s), 1)]
print(a20[0], a20[1])

Ответ: 52 53.

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