Задание 21 ЕГЭ по информатике — теория игр, полное дерево и минимакс

О чём задание

Задание 21 — финал блока теории игр (19-21) и одно из самых трудных в повышенном уровне КЕГЭ. Стоит 1 первичный балл, но за это время можно было бы решить 2-3 более лёгких задания. Поэтому в стратегии на экзамене 21 часто откладывают: сначала берут всё простое, а к 21 возвращаются в конце.

Напомню общую постановку игры — подробно в задании 19. Два игрока, Петя и Ваня, ходят по очереди. Есть одна или две кучи камней, ход — это операция над кучей (+1, +2, ×2, ×3 и т.п.). Игра заканчивается, когда количество камней достигает границы N. Побеждает тот, кто сделал последний ход. Оба играют оптимально.

Типовые формулировки задания 21

На ЕГЭ 2026 в блоке 21 встречаются:

• «У Вани есть выигрышная стратегия, которая позволяет ему выиграть при любой игре Пети, но при этом у Вани нет стратегии выиграть за 2 хода. Найди все S»
• «Найди S, при котором Ваня выигрывает, но Петя может затянуть игру так, чтобы Ваня не смог выиграть на своём первом ходу»

В 20 ты анализировал глубину 2-3 (выигрыш за 1-2 хода). В 21 дерево строится до конца — любая глубина. Это и есть минимакс в чистом виде.

Минимаксная стратегия

Минимакс — базовый алгоритм для игр с нулевой суммой (если один выиграл, другой проиграл). Идея:

• Игрок, чей ход, выбирает лучший для себя исход
• Если игрок выигрывает в хотя бы одной ветке — позиция для него выигрышная
• Если все ветки ведут в проигрыш — позиция проигрышная

Для задания 21 это формализуется так. Позиция s выигрышная для текущего игрока, если:

• Существует хотя бы один ход в позицию, которая проигрышная для соперника

Позиция проигрышная для текущего игрока, если:

• Все ходы ведут в позиции, выигрышные для соперника

Базовый случай — терминал (s >= N): тот, чей ход в терминале, проиграл (ведь ход уже сделал предыдущий игрок, и он победил).

Разметка снизу вверх

Алгоритм работы на бумаге:

1. Пометь все терминальные позиции s >= N как «игра окончена — ходивший выиграл»
2. Иди вниз по числам: для позиции s смотри, куда ведут её ходы
3. Если хоть один ход ведёт в проигрышную позицию соперника — s выигрышная
4. Если все ходы ведут в выигрышные позиции соперника — s проигрышная
5. Повторяй, пока не разметишь все позиции от 1 до N-1

Позиция для текущего	Условие
Выигрышная (W)	Существует ход в L соперника
Проигрышная (L)	Все ходы ведут в W соперника
Терминал	s >= N, игра закончилась

Python-скрипт через рекурсию с мемоизацией

Именно с 21 начинается ценность @lru_cache — без мемоизации большое дерево считается долго.

from functools import lru_cache

N = 77  # граница, значение из условия

def moves(pos):
    # пример: можно +1 или ×2
    return [pos + 1, pos * 2]

@lru_cache(maxsize=None)
def wins(pos):
    """True, если игрок, чей ход СЕЙЧАС, выигрывает при оптимальной игре."""
    if pos >= N:
        # в терминал попадаешь ПОСЛЕ хода соперника —
        # значит, соперник только что выиграл, а текущий проиграл
        return False
    # выигрываю, если есть ход, ведущий в проигрыш соперника
    return any(not wins(m) for m in moves(pos))

# Найти все S, где Петя проигрывает (значит, у Вани выигрышная стратегия)
for s in range(1, N):
    if not wins(s):
        print(s, "— у Вани выигрышная стратегия")

Это базовая версия. Для задания 21 часто нужна глубина — сколько минимум/максимум ходов до конца. Расширенная версия:

from functools import lru_cache

N = 77

def moves(pos):
    return [pos + 1, pos * 2]

@lru_cache(maxsize=None)
def solve(pos, player):
    """Возвращает (победитель, минимум_ходов_до_конца_при_оптимальной_игре).
       player: 'P' или 'V' — чей ход."""
    if pos >= N:
        # предыдущий игрок выиграл
        winner = 'V' if player == 'P' else 'P'
        return (winner, 0)
    results = [solve(m, 'V' if player == 'P' else 'P') for m in moves(pos)]
    # Ищу ход, где Я выигрываю. Если есть — беру минимум длины среди моих побед.
    my_wins = [(w, d + 1) for (w, d) in results if w == player]
    if my_wins:
        return min(my_wins, key=lambda x: x[1])
    # Я проигрываю при любой игре. Беру максимум длины (соперник может затянуть).
    return max([(w, d + 1) for (w, d) in results], key=lambda x: x[1])

print(solve(10, 'P'))  # победитель и длина игры

С такой версией ты ответишь на любой вопрос задания 21: кто выигрывает, за сколько ходов, может ли соперник затянуть и на сколько.

Разбор примера

Условие. Два игрока, Петя и Ваня, играют в игру. Есть куча из S камней. Ходы: добавить 1 камень или удвоить количество. Петя ходит первым. Игра заканчивается, когда камней становится не меньше 77. Побеждает тот, кто сделал последний ход.

Задание 21. Найди наименьшее значение S, при котором у Вани есть выигрышная стратегия, причём Ваня не может выиграть за один ход, а Петя может играть так, чтобы Ваня выиграл только на своём втором ходу (не раньше).

Шаг 1. Разметка терминалов и В1

Терминал — s >= 77. Если s от 39 до 76, удвоение даёт >= 77, значит позиция В1 для ходящего. Если s = 76, +1 тоже ведёт в терминал. Получается, В1 для ходящего — все s от 39 до 76.

Шаг 2. П1 — проигрыш за 1 ход соперника

Позиция П1 — все ходы из неё ведут в В1 соперника. Ищем s, такие что и s+1, и 2·s лежат в [39, 76].

• 2·s в [39, 76] -> s в [20, 38]
• s+1 в [39, 76] -> s в [38, 75]
• Пересечение: s = 38 (единственная П1 в этом слое)

Шаг 3. В2 для Вани

В2 — есть ход из s в П1. Нам нужно, чтобы s = 38 достигалось от текущей позиции.

• s+1 = 38 -> s = 37
• 2·s = 38 -> s = 19

Позиции 37 и 19 — В2 для ходящего (то есть для Вани, если Петя уже сделал первый ход).

Шаг 4. П2 для Пети

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

Позиции «Петя проигрывает»: все ходы Пети ведут в W-позиции Вани.

• S = 36: Петя ходит +1 -> 37 (В2 Вани, Ваня выигрывает за 2). Петя ×2 -> 72 (В1 Вани). Обе W для Вани. Но S=36 — сама В1 для Пети (36×2=72 > 77? нет, 72 < 77, значит s=36 не терминал, 2·36=72 — а это В1 Вани, значит Петя дал Ване победу за 1 ход). Упс, значит S=36 проигрышная для Пети, и Ваня выигрывает за 1 — не подходит.

Нужно найти наименьшее S, где:

• Оба хода Пети ведут в W-позиции Вани (Ваня побеждает)
• Ни один ход Пети не ведёт в В1 Вани (иначе Ваня выигрывает за 1, а нам надо за 2)
• Есть ход Пети в В2 Вани (Ваня выигрывает за 2)

Значит, оба хода Пети должны попадать либо в В2 (s=37 или 19), либо в какие-то ещё W-позиции, но не в В1.

Проверим S = 18: 18+1 = 19 (В2 Вани), 2·18 = 36 (что это?). 36 — не В1 (36 < 39). 36 — П1 для того, кто ходит? У Вани ход из 36. 36+1 = 37 (В2 Вани? нет, В2 для того, кто ходит — из 37 ходит Петя после удара Вани). Запутался? Это главная причина писать код.

Запустим наш solve:

N = 77
for s in range(1, 39):
    winner, depth = solve(s, 'P')
    if winner == 'V':
        print(s, winner, depth)

Скрипт покажет, какие S дают победу Вани и с какой минимальной глубиной игры. Наименьшее S, где Ваня побеждает ровно на 2-м своём ходу (глубина 4 полуходов — Петя-Ваня-Петя-Ваня), и будет ответом.

Ручная разметка занимает 15-20 минут, скрипт — 5 секунд. Поэтому код на тренировке обязателен.

Типичные ошибки

1. Неверная разметка терминалов. Путаница между s >= N и s > N. Между «победил сделавший последний ход» и «победил не сделавший последний ход» (такие варианты тоже бывают). Читай условие дважды.

2. Пропуск квантора «для всех». Если Ваня выигрывает «при любой игре Пети» — ты должен проверить все первые ходы Пети. Нашёл один вариант, где Ваня не выигрывает — весь S не подходит.

3. Кто в корне. В корне дерева ходит Петя. Если ты написал solve(s, 'V') — ответ неправильный.

4. Мемоизация по позиции без игрока. Если у тебя wins(pos) без аргумента-игрока, ты предполагаешь, что игра симметрична (оба игрока ходят одинаковыми ходами). В большинстве задач ЕГЭ это так, но прочитай условие — иногда ходы разные.

5. Забыл про «затянуть игру». В некоторых формулировках 21 нужно найти, насколько Петя может продлить. Это максимум длины среди проигрышных веток. max вместо min.

6. Переполнение рекурсии. Если диапазон большой (N > 1000), стандартная рекурсия Python упадёт. Поставь sys.setrecursionlimit(10**6) или перепиши через стек/итерацию.

Больше про подводные камни — в статье Типичные ошибки в ЕГЭ по информатике.

Тайминг на экзамене

КЕГЭ длится 235 минут на 27 заданий. Для задания 21:

• 15 минут — максимум, который стоит на нём сидеть без прогресса
• Если за 5 минут не понял условие — пропусти и вернись в конце
• Решай 21 после 22-25 (там тоже код и есть шанс набрать ещё 4 балла)

Распределение по блокам 19-21: 30-40 минут. Это второй по времени затратности блок после 26-27 (там 40-60 минут на два задания).

Разбор конкретной демо-задачи на игры — в разборе демоверсии ЕГЭ 2026.

Мини-чеклист перед решением

• Понял условие: ходы, граница, кто первый, критерий победы
• Проверил терминалы на бумаге
• Написал solve с @lru_cache (на тренировке — всегда!)
• В корне ходит Петя, значит solve(S, 'P')
• Проверил результат ручной разметкой на 2-3 примерах
• Учёл квантор «для всех» / «существует» в формулировке
• Ответ — именно то, что просят (наименьшее/наибольшее/сумма)

Что читать дальше

• Задание 19 ЕГЭ по информатике — основа блока игр, стратегия на 1 ход
• Задание 20 ЕГЭ по информатике — стратегия за 1-2 хода, дерево глубины 2-3
• Python-идиомы для ЕГЭ — lru_cache, рекурсия, генераторы
• Как набрать 90 баллов на ЕГЭ по информатике — стратегия всего экзамена
• Разбор демоверсии ЕГЭ по информатике 2026 — актуальные формулировки ФИПИ