Задание 20 ЕГЭ по информатике — теория игр, выигрыш Пети вторым ходом
Как решать задание 20 ЕГЭ по информатике: Петя не выигрывает первым ходом, но выигрывает своим вторым при любой игре Вани. Разметка позиций, разбор классической задачи и Python-скрипт.
О чём задание
Задание 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 — все позиции, откуда есть ход в финал
- Пометь П1 — все позиции, где все ходы ведут в В1
- Пометь В2 — позиции, где есть ход в П1
- И так далее до нужной глубины
Главный подвох: метки относятся к тому игроку, чей ход сейчас. Когда ты стоишь в позиции s и размечаешь её как «В1», это значит «текущий ходящий игрок выигрывает за 1 ход» — неважно, Петя это или Ваня. Поэтому при построении дерева подписывай в каждой вершине, чей сейчас ход: одна и та же позиция для одного игрока выигрышная, а для другого была бы проигрышной.
Пошаговый разбор классической задачи
Условие. Два игрока, Петя и Ваня, играют в игру. Перед ними куча камней. Игроки ходят по очереди, Петя первым. За один ход можно добавить в кучу 1 камень или увеличить количество камней в куче в 2 раза. Игра заканчивается, когда камней становится не менее 33. Победителем считается игрок, сделавший последний ход.
Задание 20. Для игры найди два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от игры Вани. Укажи эти значения в порядке возрастания.
Шаг 1. Размечаем позиции В1
Позиция В1 для Пети — такая S, откуда один его ход даёт >= 33. Удвоение срабатывает при любом S >= 17 (даёт не меньше 34), а ход +1 — только из S = 32 (даёт ровно 33). Значит, В1 — все S от 17 до 32.
Шаг 2. Ищем П1 (это позиции Вани после первого хода Пети)
Разберёмся, что должно произойти. Петя сейчас в позиции S. Он делает ход — получается S+1 или 2S, и наступает ход Вани. Чтобы Петя гарантированно выиграл своим вторым ходом, после любого хода Вани позиция должна оказаться В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', из которых удвоение сразу даёт 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):
"""Метка позиции для игрока, который сейчас ходит:
'END' — игра уже окончена (победил предыдущий игрок),
'W1' — выигрывает своим первым ходом,
'L1' — проигрывает: любой ход отдаёт сопернику выигрыш за 1 ход,
'W2' — выигрывает не позже второго хода,
'deep' — исход решается глубже, для задания 20 не важен.
"""
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/П1 относится к текущему ходящему, а не к Пете. Когда строишь дерево, подписывай: «ход Пети» / «ход Вани».
-
Забыл, что В1 не исключает В2. Позиция S, которая уже В1 (Петя может выиграть за 1 ход), тоже в каком-то смысле В2 (он может выиграть за <= 2 хода). В условии обычно просят В2, которые не В1 — внимательно читай «не может выиграть первым ходом, но может вторым».
-
Неверные границы финала. «Не менее 33» =
s >= 33. А «больше 33» =s > 33. Разница в 1 камень меняет весь ответ. -
Упустил один из ходов. Если в игре 3 операции (+1, +2, ×2), а ты в дереве нарисовал 2 ветки — ответ неверный. Рисуй все ходы.
Разбор наиболее частых ошибок на экзамене — в статье Типичные ошибки в ЕГЭ по информатике.
Тайминг на экзамене
КЕГЭ идёт 235 минут, в нём 27 заданий. На задания 19-21 суммарно закладывай 30-40 минут. Примерное распределение:
- 19 — 8-10 минут (разминка, самое простое в блоке)
- 20 — 10-12 минут (нужно построить дерево глубиной 2-3)
- 21 — 12-15 минут (полное дерево + минимакс)
Если видишь, что застрял — пометь задание и иди дальше. Задания 22-26 зачастую быстрее, чем 20. Вернёшься к игре с ясной головой. Про распределение времени подробно в плане подготовки на 3 месяца.
Мини-чеклист перед решением
- Понял условие: какие ходы, когда финал, кто первый
- Выписал начальное S и границу N
- Нарисовал дерево, подписал чей ход в каждой вершине
- Разметил финалы, потом В1, потом П1, потом В2
- Проверил для всех ходов соперника на каждом уровне
- Убедился, что позиция не В1 если требуется «не первым ходом»
- Выписал наименьшие/наибольшие значения в нужном порядке
Пройди по этому списку — и задание 20 сведётся к механической работе: вся его сложность не в идеях, а в аккуратной записи.
Что читать дальше
- Задание 19 ЕГЭ по информатике — основы теории игр, первый ход победителя
- Задание 21 ЕГЭ по информатике — самое сложное в блоке игр, полное дерево и минимакс
- Разбор демоверсии ЕГЭ по информатике 2026 — актуальные формулировки
- Как набрать 90 баллов на ЕГЭ по информатике — стратегия на весь экзамен
Потренировать разметку позиций можно в TuteMe: задачи блока 19–21 с автопроверкой и разбором, в котором дерево игры уже размечено — удобно сверять со своим.