Задание 21 ЕГЭ по информатике: дерево игры и выигрышная стратегия

В заданиях 19 и 20 выигрышную стратегию ищут для Пети — того, кто ходит первым. Задание 21 переворачивает роль: стратегию нужно построить для Вани, второго игрока. Из-за этого меняется порядок кванторов «существует» / «для любого», а вместе с ним — и вся логика решения.

Стратегия Пети (задание 20) устроена так: Петя один раз выбирает свой первый ход, а дальше должен победить для любого ответа Вани. Формально: «$\exists$ ход Пети такой, что $\forall$ ход Вани Петя выигрывает вторым ходом».

Стратегия Вани (задание 21) устроена наоборот: Ваня не выбирает, с чего начнётся игра, — первый ход уже сделал Петя, и он мог сделать любой из своих ходов. Ваня должен победить, каким бы ни был этот первый ход. Формально: «$\forall$ ход Пети $\exists$ ход Вани такой, что Ваня побеждает». Квантор «для любого» стоит первым и относится к сопернику, а не к самому Ване — это и есть источник дополнительной сложности.

Добавьте к этому, что выигрыш нужно получить не «когда-нибудь потом», а строго в один из двух конкретных моментов — на первом или на втором ходу Вани, — и кванторная конструкция становится трёхэтажной: «для любого хода Пети существует ход Вани, такой что либо игра заканчивается сразу, либо для любого ответного хода Пети существует завершающий ход Вани». Именно эта вложенность кванторов и делает задание 21 заданием высокого уровня, а не технической разницей в арифметике.

Второе условие задания — «у Вани НЕТ стратегии выиграть гарантированно первым ходом» — добавляет проверку в обратную сторону: нужно убедиться, что хотя бы один ответ Пети не даёт Ване закончить игру сразу, иначе задача превращается в задание 19 и берётся не то значение S.

Чтобы не путаться в дереве игры, каждой позиции удобно присвоить метку — чей сейчас ход и который он по счёту:

• П1 — начальная позиция, из неё делает свой первый ход Петя.
• В1 — позиция после первого хода Пети, из неё делает свой первый ход Ваня.
• П2 — позиция после первого хода Вани, из неё делает свой второй ход Петя.
• В2 — позиция после второго хода Пети, из неё делает свой второй ход Ваня.

Формальные определения через кванторы

Позиция называется терминальной, если сумма камней в ней уже не меньше порога T. Как только терминальная позиция получена, игра заканчивается и выигрывает тот, кто сделал последний ход, — новых ходов из терминальной позиции не делает никто.

«Ваня выигрывает не позднее чем своим k-м ходом из позиции X» (запишем это как $W(X, k)$) определяется рекурсивно:

• $W(X, k)$ истинно, если существует ход Вани из X, ведущий сразу в терминальную позицию (Ваня побеждает немедленно) — тогда k может быть любым, хоть 1;
• иначе, при $k \ge 2$, $W(X, k)$ истинно, если существует «неторопливый» ход Вани в позицию Y (нетерминальную), такой что для любого ответного хода Пети из Y в позицию Z верно: Z не терминальна (иначе выиграл бы Петя) и $W(Z, k - 1)$ истинно;
• во всех остальных случаях $W(X, k)$ ложно.

Условие задания 21 через эту запись выглядит компактно. Обозначим начальную позицию П1 буквой I. Тогда нужное S — то, для которого:

Первая половина — это «у Вани есть стратегия выиграть первым или вторым ходом при любой игре Пети». Вторая половина — это «у Вани нет стратегии выиграть гарантированно первым ходом»: достаточно, чтобы хотя бы один ход Пети не позволял Ване закрыть партию сразу же.

Дерево игры строится слой за слоем: корень — позиция П1, дальше каждый слой — все возможные ходы того игрока, чья очередь. Правило построения простое: из каждой позиции проведите по одной ветке на каждый допустимый ход (обычно их две — «+1» и «×2», а если куч несколько, то по два варианта на каждую кучу). Позицию с суммой (или произведением, смотря какое у игры условие окончания) не меньше порога T дальше не разворачивайте — она терминальна, партия в ней уже закончена.

Разберём мини-игру с одной кучей на маленьких числах — правила те же, что и в задании 21, только порог маленький, чтобы дерево уместилось целиком. Порог $T = 11$, в куче $S = 3$ камня, ход — «+1» или «×2»:

• П1: 3 — ход Пети.
  • Петя играет «+1» → В1: 4 (не терминал, Ваня не может закончить: 4+1=5, 4×2=8, оба меньше 11).
    • Ваня играет «+1» → П2: 5 (не терминал).
      • Петя играет «+1» → В2: 6. Ваня завершает: 6×2=12 ≥ 11. Ваня побеждает.
      • Петя играет «×2» → В2: 10. Ваня завершает: 10+1=11 ≥ 11. Ваня побеждает.
      Оба ответа Пети из позиции 5 дают Ване выигрыш вторым ходом — ветка «Ваня играет 5» рабочая.
    • Ваня играет «×2» → П2: 8 (не терминал) — альтернатива, показываем для контраста.
      • Петя играет «+1» → В2: 9. Ваня завершает: 9×2=18 ≥ 11. Ваня побеждает.
      • Петя играет «×2» → 16 ≥ 11 — терминал, и последний ход сделал Петя. Петя побеждает.
      Эта ветка Ваню не спасает: Петя может ответить «×2» и выиграть сам. Значит, из 4 Ваня обязан играть именно 5, а не 8.
  • Петя играет «×2» → В1: 6. Ваня завершает сразу: 6×2=12 ≥ 11. Ваня побеждает первым ходом.

Итог по дереву: что бы ни сыграл Петя первым ходом (4 или 6), у Вани находится ответ, гарантирующий победу не позднее второго хода (для 6 — сразу первым ходом, для 4 — вторым ходом через промежуточную позицию 5). При этом не для любого первого хода Пети Ваня выигрывает немедленно — ветка «Петя играет 4» требует второго хода. Значит, S = 3 при T = 11 одновременно удовлетворяет обоим условиям задания 21: выигрыш не позднее второго хода есть, а гарантии выигрыша ровно первым ходом — нет.

Именно так и читается дерево на экзамене: сверху вниз по уровням П1 → В1 → П2 → В2, на каждом уровне держим в уме, чей это ход, и на каждом ходе Пети (уровни П1 и П2) проверяем все его варианты, а на каждом ходе Вани (уровни В1 и П2 → В2) достаточно найти один подходящий.

Дерево вручную удобно строить только для маленьких порогов. На реальных числах ФИПИ (порог 50–150, две кучи по 4 хода в каждой позиции) дерево разрастается быстро, и его перебирают программой — рекурсией с мемоизацией. Ниже код для игры с двумя кучами и порогом по сумме камней (это самый частый вариант условия); для одной кучи или для порога по произведению меняются только функции $\text{moves}$ и $\text{is\_final}$.

from functools import lru_cache

T = 59

def moves(state):
    a, b = state
    return [(a + 1, b), (a, b + 1), (2 * a, b), (a, 2 * b)]

@lru_cache(maxsize=None)
def is_final(state):
    return sum(state) >= T

@lru_cache(maxsize=None)
def can_finish_now(state):
    return any(is_final(nxt) for nxt in moves(state))

@lru_cache(maxsize=None)
def wins_in_le(state, k):
    if k <= 0:
        return False
    if can_finish_now(state):
        return True
    if k == 1:
        return False
    for my_move in moves(state):
        if is_final(my_move):
            continue
        if all(
            not is_final(reply) and wins_in_le(reply, k - 1)
            for reply in moves(my_move)
        ):
            return True
    return False

def opponent_finishes_after_any_reply(state):
    for reply in moves(state):
        if is_final(reply):
            return False
        if not can_finish_now(reply):
            return False
    return True

Функция $\text{wins\_in\_le(state, k)}$ — это прямая запись рекурсивного определения $W(X, k)$ из предыдущего блока: «существует ход, завершающий игру сразу, а если нет — существует ход в нетерминальную позицию, такой что для ЛЮБОГО ответа соперника (сам нетерминальный) удаётся выиграть не позднее $k-1$ следующих ходов». Три конкретных задания блока — это три способа применить одни и те же функции к позиции П1:

def task19(a0, s_max):
    for S in range(1, s_max + 1):
        I = (a0, S)
        if is_final(I):
            continue
        if any(not is_final(p1) and can_finish_now(p1) for p1 in moves(I)):
            return S
    return None

def task20(a0, s_max):
    found = []
    for S in range(1, s_max + 1):
        I = (a0, S)
        if is_final(I):
            continue
        if any(is_final(p1) for p1 in moves(I)):
            continue
        if any(opponent_finishes_after_any_reply(p1) for p1 in moves(I)):
            found.append(S)
        if len(found) == 2:
            break
    return found

def task21(a0, s_max):
    found = []
    for S in range(1, s_max + 1):
        I = (a0, S)
        if is_final(I):
            continue
        p1_list = moves(I)
        if any(is_final(p1) for p1 in p1_list):
            continue
        if not all(wins_in_le(p1, 2) for p1 in p1_list):
            continue
        if not any(not wins_in_le(p1, 1) for p1 in p1_list):
            continue
        found.append(S)
    return found

print(task19(5, 53))
print(task20(5, 53))
print(task21(5, 53))

Запуск на данных реального задания (пять камней в первой куче, порог 59, $1 \le S \le 53$) даёт $\text{task19} = 14$, $\text{task20} = [24, 26]$ и $\text{task21} = [23, 25]$ — то есть 23 как наименьшее значение для задания 21. Все три числа совпадают с эталонами открытого банка ФИПИ для этого варианта.

Программа быстро находит число, но на экзамене компьютера с Python не будет — задание 21 всё же решается на черновике рассуждением, а не перебором всех S от 1 до 53. Проверка вручную для конкретного кандидата S строится в три шага.

1. Выпишите все ходы Пети из начальной позиции (обычно их четыре: «+1» к каждой куче и «×2» для каждой кучи). Для каждого сразу отбросьте те, что уже завершают игру, — они дают победу Пете и автоматически проваливают всю проверку для этого S.
2. Для каждого оставшегося хода Пети проверьте, может ли Ваня закончить партию одним ходом (прибавьте 1 к каждой куче и удвойте каждую кучу — хотя бы один результат должен достичь порога). Если да — эта ветка Пети закрыта на первом ходу Вани, дальше её не разворачивайте.
3. Для веток, не закрытых на первом ходу, повторите тот же перебор ещё на один уровень глубже: переберите ходы Вани, а для каждого — ВСЕ ответы Пети, и для каждого такого ответа проверьте, что Ваня снова может закончить партию одним ходом. Если для какого-то хода Вани это верно при любом ответе Пети — ветка закрыта на втором ходу.

Если после этого разбора все ветки Пети закрыты (первым или вторым ходом Вани) — первое условие выполнено. Если хотя бы одна ветка Пети не закрылась на первом ходу Вани — выполнено и второе условие. S, для которого верно и то и другое, и есть решение; если решений несколько, берите наименьшее. На реальных числах ФИПИ полезно сначала прикинуть диапазон S перебором сверху (у больших S Ваня почти всегда выигрывает первым ходом — второе условие не выполняется) и снизу (у маленьких S Петя обычно успевает выиграть сам), а затем сузить поиск до нескольких кандидатов и проверить их руками по описанному алгоритму.

Простое правило: если ищете стратегию Пети — это задание 20; если стратегию Вани и в условии есть слова «первым или вторым ходом» — это задание 21.

Начните с заданий 19 и 20 — они проще и вводят тот же аппарат (ходы, терминальная позиция, «выигрышная стратегия»). Прорешайте 10–15 вариантов 19-го и 20-го заданий, каждый раз явно выписывая все ходы из начальной позиции. Это закладывает базу для 21-го.

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

Отрабатывайте задания с условием и по сумме, и по произведению камней — они попадаются в банке примерно поровну. Засекайте время: цель — укладываться в 10 минут, отведённые ФИПИ на это задание, оставляя запас на остальные 26 заданий работы.

Решайте задания 19, 20 и 21 подряд для одного и того же варианта — так вы научитесь удерживать в голове общее условие и не путать, какая стратегия и для кого именно нужна в каждом из трёх заданий. Завершите подготовку пробным экзаменом КЕГЭ целиком, чтобы увидеть задание 21 в контексте всей работы.