Задание 20 ЕГЭ по информатике — теория игр, стратегия за 1 или 2 хода

О чём задание

Задание 20 — это второе задание в блоке теории игр (19, 20, 21). Стоит 1 первичный балл и идёт в повышенном уровне сложности. В отличие от задания 19, где ты анализируешь только первый ход победителя, здесь нужно заглянуть на 2 хода вперёд.

Напомню общую постановку игры (подробно — в статье про задание 19): есть куча камней (или две кучи), двое игроков ходят по очереди, Петя ходит первым. Ход — это какая-то операция над кучей (добавить камень, удвоить, утроить). Выигрывает тот, после чьего хода количество камней достигает заданной границы N. Оба игрока играют оптимально.

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

На ЕГЭ 2026 встречаются два варианта:

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

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

Разметка позиций: В1, В2, П1

Чтобы решать задание 20 без путаницы, нужна система обозначений. Позиция — это число камней (или пара для двух куч). В каждой вершине дерева пишем:

Метка	Что значит	Формальное условие
Финал	Позиция уже >= N, игра закончена	s >= N
В1	Тот, кто ходит, выигрывает за 1 ход	Существует ход в финал
П1	Все ходы ведут в В1 соперника	Все ходы -> В1
В2	Есть ход в П1 соперника	Существует ход -> П1
П2	Все ходы ведут в В1 или В2	Все ходы -> В1 или В2

Алгоритм разметки работает снизу вверх:

1. Пометь финальные позиции (игра закончена)
2. Пометь В1 — все позиции, откуда есть ход в финал
3. Пометь П1 — все позиции, где все ходы ведут в В1
4. Пометь В2 — позиции, где есть ход в П1
5. И так далее до нужной глубины

Главный подвох: метки относятся к тому игроку, чей ход сейчас. Когда ты стоишь в позиции s и размечаешь её как «В1», это значит «текущий ходящий игрок выигрывает за 1». После его хода соперник окажется в финале — для соперника эта же позиция была П1 (все ходы ведут в В1... нет, финал уже — так что и обсуждать нечего).

Пошаговый разбор классической задачи

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

Задание 20. Для игры найди два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от игры Вани. Укажи эти значения в порядке возрастания.

Шаг 1. Решаем задание 19 как часть 20

Позиция В1 для Пети — такая S, откуда один его ход даёт >= 33. Это S от 17 до 32 (удвоение 17 -> 34, удвоение 32 -> 64, а +1 работает только с S=32). Если точнее: удвоение подходит при S >= 17, +1 при S = 32. Значит:

• S = 32: В1 (ход +1 даёт 33)
• S от 17 до 32: В1 (удвоение даёт >= 34)

Шаг 2. Ищем П1 (это позиции Вани после первого хода Пети)

Нам нужны такие S, чтобы оба хода Пети вели в позицию П1 для Вани — тогда Петя не может выиграть за 1 ход, но гарантированно выигрывает на 2-м ходу.

Стоп. Порядок другой. Петя сейчас в позиции S. Пусть он ходит — получаем S+1 или 2S, и теперь ход Вани. Чтобы Петя выиграл на своём 2-м ходу, нужно, чтобы после хода Вани позиция стала В1 для Пети. Значит, позиция после хода Пети должна быть П1 для Вани (все ходы Вани ведут в В1 для Пети).

П1 для Вани = все ходы из S' ведут в В1 для Пети = и S'+1, и 2·S' лежат в диапазоне [17, 32] или равны 32 (то есть в В1).

Проверим S' = 16: 16+1 = 17 (В1), 2·16 = 32 (В1). Оба в В1 -> S' = 16 это П1. Проверим S' = 15: 15+1 = 16 (не В1!), значит не П1. Проверим S' = 8: 8+1 = 9 (не В1), нет.

Значит единственная П1 в интересном диапазоне — это S' = 16 (удвоение даёт 32, +1 даёт 17 — обе в В1).

Проверим ещё: S' такое, что 2·S' >= 33 (это уже финал — значит Ваня выиграет за 1 ход, позиция В1 для Вани, не подходит).

Шаг 3. Ищем В2 для Пети

В2 — это позиции S, где существует ход Пети в П1 Вани (S' = 16), и при этом S не является В1 (Петя не может выиграть за 1 ход).

• S = 15: 15+1 = 16 (П1), не В1. Подходит.
• S = 8: 2·8 = 16 (П1), не В1. Подходит.

Оба наименьших значения: 8 и 15.

Проверка условия «независимо от игры Вани»

Из S = 8: Петя удваивает -> 16 (П1 для Вани). Ваня ходит:

• Ваня +1 -> 17 (В1 для Пети) — Петя удваивает -> 34, победа
• Ваня удваивает -> 32 (В1 для Пети) — Петя +1 -> 33, победа

Действительно, любой ход Вани ведёт к проигрышу. Стратегия сработала.

Python-скрипт для перебора

Когда готовишься, полезно написать скрипт — он быстро даст ответ и проверит твою ручную разметку.

from functools import lru_cache

N = 33

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

@lru_cache(maxsize=None)
def status(s):
    """Возвращает минимальное число ходов до победы текущего игрока.
       0 — текущий игрок уже в финале (проиграл, последний ход не его).
       Иначе — минимум по ходам из (1 + status соперника наоборот).
       Упрощённо: возвращаем 'W1', 'W2', 'L1', 'L2', 'deep'.
    """
    if s >= N:
        return "END"  # предыдущий игрок выиграл
    next_states = [status(m) for m in moves(s)]
    # В1: есть ход в END
    if "END" in next_states:
        return "W1"
    # П1: все ходы ведут в W1 соперника
    if all(x == "W1" for x in next_states):
        return "L1"
    # В2: есть ход в L1
    if "L1" in next_states:
        return "W2"
    return "deep"

for s in range(1, N):
    print(s, status(s))

Запусти и найди все позиции с меткой W2, где при этом Петя не может выиграть за 1 ход (W1). Ответ: 8 и 15.

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

Задание 20 коварно не алгоритмически, а логически. Вот что часто идёт не так:

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

2. Перепутал чей ход в вершине. Метка В1/П1 относится к текущему ходящему, а не к Пете. Когда строишь дерево, подписывай: «ход Пети» / «ход Вани».

3. Забыл, что В1 не исключает В2. Позиция S, которая уже В1 (Петя может выиграть за 1 ход), тоже в каком-то смысле В2 (он может выиграть за <= 2 хода). В условии обычно просят В2, которые не В1 — внимательно читай «не может выиграть первым ходом, но может вторым».

4. Неверные границы финала. «Не менее 33» = s >= 33. А «больше 33» = s > 33. Разница в 1 камень меняет весь ответ.

5. Упустил один из ходов. Если в игре 3 операции (+1, +2, ×2), а ты в дереве нарисовал 2 ветки — ответ неверный. Рисуй все ходы.

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

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

КЕГЭ идёт 235 минут, в нём 27 заданий. На задания 19-21 суммарно закладывай 30-40 минут. Примерное распределение:

• 19 — 8-10 минут (разминка, самое простое в блоке)
• 20 — 10-12 минут (нужно построить дерево глубиной 2-3)
• 21 — 12-18 минут (полное дерево + минимакс)

Если видишь, что застрял — пометь задание и иди дальше. Задания 22-26 зачастую быстрее, чем 20. Вернёшься к игре с ясной головой. Про распределение времени подробно в плане подготовки на 3 месяца.

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

• Понял условие: какие ходы, когда финал, кто первый
• Выписал начальное S и границу N
• Нарисовал дерево, подписал чей ход в каждой вершине
• Разметил финалы, потом В1, потом П1, потом В2
• Проверил для всех ходов соперника на каждом уровне
• Убедился, что позиция не В1 если требуется «не первым ходом»
• Выписал наименьшие/наибольшие значения в нужном порядке

Если выполнить этот чеклист — задание 20 становится механическим. Основная сложность — дисциплина записи и внимательность.

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

• Задание 19 ЕГЭ по информатике — основы теории игр, первый ход победителя
• Задание 21 ЕГЭ по информатике — самое сложное в блоке игр, полное дерево и минимакс
• Разбор демоверсии ЕГЭ по информатике 2026 — актуальные формулировки
• Как набрать 90 баллов на ЕГЭ по информатике — стратегия на весь экзамен