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

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

Пример

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

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

Например, пусть в одной куче 17 камней, а в другой 23 камня; такую позицию в игре обозначим (17, 23). Тогда за один ход можно получить любую из шести позиций: (19, 23), (17, 25), (24, 23), (17, 30), (34, 23), (17, 46).

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

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

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

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

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

Решение

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

Подходят S = 14, 21, 25, 26, 27. Нужны два наименьших из них.

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

(6, 28) → (6, 56)
(11, 28) → (11, 56)
(8, 28) → (8, 56)
(4, 30) → (4, 60)
(4, 35) → (4, 70)
(4, 56) → (6, 56)

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

from functools import lru_cache


def moves(p):
    a, b = p
    return [(a + 2, b), (a + 7, b), (a * 2, b), (a, b + 2), (a, b + 7), (a, b * 2)]


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


@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, 58)
a20 = [s for s in R if f((4, s), 3) and not f((4, s), 1)]
print(a20[0], a20[1])

Ответ: 14 21.

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