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

О чём задание

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

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

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

На ЕГЭ 2026 в задании 21 встречаются такие формулировки:

• «У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая гарантирует победу первым ходом. Найди все 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. Ищем S, где проигрывает уже Петя

В корне ходит Петя, и нам нужна позиция, где он проигрывает нужным образом. Два условия:

• все ходы Пети ведут в выигрышные позиции Вани (В1 или В2) — иначе у Пети нашёлся бы спасительный ход;
• хотя бы один ход Пети ведёт именно в В2 — этим ходом Петя «затягивает» игру, и Ваня выигрывает только вторым ходом, а не первым.

Проверяем кандидатов. Ходы Пети из S — это S+1 и 2·S, и оба должны попасть в множество В1 ∪ В2 = [39; 76] ∪ {19, 37}:

• 2·S попадает туда только при S от 20 до 38 (удвоение даёт 40–76);
• S+1 попадает при S от 38 до 75, либо S+1 = 19 (S = 18), либо S+1 = 37 (S = 36).

Пересечение: S = 38 и S = 36. Но 38 — это П1 (Ваня выигрывает первым ходом, не вторым), отбрасываем. Остаётся S = 36:

• Петя ходит +1 → 37: это В2 Вани — Ваня выиграет своим вторым ходом;
• Петя ходит ×2 → 72: это В1 Вани — Ваня выиграет сразу.

Оба хода отдают победу Ване, а ход +1 позволяет Пете затянуть игру до второго хода Вани — ровно то, что требует условие.

Ответ: 36.

Проверим цепочку целиком: 36 → (Петя +1) → 37 → (Ваня +1) → 38 → (Петя, любой ход) → В1 Вани → (Ваня) → финал. Ваня побеждает своим вторым ходом, раньше — не может, как бы ни играл, если Петя тянет время.

Ручная разметка занимает 15-20 минут, скрипт из предыдущего раздела — 5 секунд и сразу показывает все слои (В1: 39–76, П1: 38, В2: 19 и 37, П2: 36). Поэтому код на тренировке обязателен: он ловит ровно те места, где в ручном дереве легко перепутать, чей ход.

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

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: на эти два задания уходит 70-100 минут — 30-40 на задание 26 и 40-60 на задание 27.

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

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

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

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

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

В TuteMe задание 21 тренируется вместе со всем блоком 19–21: автопроверка, размеченное дерево позиций в разборе и редактор Python рядом с условием.

Попробовать бесплатно →