Задание 21 ЕГЭ по информатике: дерево игры и выигрышная стратегия
Задание 21 ЕГЭ по информатике (КЕГЭ) — самое сложное задание блока «теория игр». За него дают 1 первичный балл, оно относится к высокому уровню сложности, а по обобщённому плану ФИПИ на него отводится примерно 11 минут — больше, чем на любое другое задание из первой половины работы. Ответ — целое число. Условие игры задание не повторяет: оно продолжает задания 19 и 20 общим стимулом. В статье — полная теория построения дерева игры, формальные определения позиций, рабочий Python-решатель с рекурсией и мемоизацией сразу для всех трёх заданий блока и три разбора реальных заданий из открытого банка ФИПИ с проверенными ответами. Потренироваться можно на реальных заданиях 21 ЕГЭ по информатике онлайн — с мгновенной проверкой ответа.
Что проверяет задание 21 ЕГЭ по информатике
Задания 19, 20 и 21 — единственный на КЕГЭ блок с общим условием. Условие игры целиком приводится один раз, в задании 19; задания 20 и 21 своей копии условия не имеют и начинаются словами «Для игры, описанной выше…», то есть для той же самой игры, что и в задании 19. Все три задания стоят по 1 баллу и проверяют разные умения на одном и том же материале:
Проверяемые умения (КЭС 2.15, требование 2.1):
- Задание 19 — существование ситуации: найти S, при котором Ваня выигрывает своим первым ходом после конкретного (пусть даже одного) неудачного хода Пети;
- Задание 20 — выигрышная стратегия ПЕТИ, гарантирующая победу вторым ходом независимо от игры Вани;
- Задание 21 (наша линия) — самое сложное из трёх: выигрышная стратегия ВАНИ (второго игрока), причём с двойным ограничением — выиграть первым или вторым ходом при любой игре Пети, но НЕ иметь стратегии, гарантирующей выигрыш ровно первым ходом;
- умение строить и читать полное дерево игры с учётом всех возможных ходов обоих игроков;
- умение работать с формальным определением «выигрышная стратегия — это когда игрок побеждает при ЛЮБЫХ ходах противника».
Все числовые факты об экзамене в этой статье взяты по спецификации ФИПИ 2026 года; проекты КИМ-2027 ФИПИ публикует в конце августа 2026 года, а структура работы не менялась с 2025 года.
| Параметр | Значение |
|---|---|
| Максимальный балл | 1 первичный (частичного зачёта нет: только полное совпадение с эталоном) |
| Уровень сложности | Высокий (В) — одно из пяти заданий этого уровня во всей работе |
| КЭС | 2.15 — тот же элемент содержания, что и у заданий 19 и 20 |
| Код требования | 2.1 |
| Форма ответа | Краткий: одно целое число |
| Файл к заданию | Нет, специализированное ПО не требуется |
| Примерное время выполнения | 11 минут (обобщённый план варианта КИМ, СПЕЦ-2026) |
| Связанные задания | Задание 19 (то же условие игры, существование ситуации) и задание 20 (то же условие, стратегия Пети вторым ходом) |
Тренируйтесь на реальных заданиях банка ФИПИ
Задания 21 ЕГЭ по информатике с мгновенной проверкой ответа. Решаем, ошибаемся, разбираем — бесплатно.
Как выглядит формулировка
Условие игры (общее для 19, 20 и 21) описывает камни в кучах и два возможных хода. Вот формулировка из реального задания открытого банка ФИПИ:
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах оказывается 59 или больше камней. В начальный момент в первой куче было пять камней, во второй куче – S камней; . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.»
А дальше идёт собственно задание 21: «Для игры, описанной выше, найдите минимальное значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Если найдено несколько значений S, в ответе укажите наименьшее из них.»
От варианта к варианту меняются: количество куч (одна или две), начальные значения, порог окончания игры (сумма или произведение камней в кучах) и формулировка задания 21 всегда одна и та же — «выиграть первым ИЛИ вторым ходом, но НЕ гарантированно первым». Ответ — одно целое число, записывается без пробелов и других символов. Если условию удовлетворяет несколько значений S, в ответ идёт наименьшее — эту фразу в конце формулировки пропускать нельзя.
Теория: всё, что нужно для задания 21
Почему это задание высокого уровня: выигрывает ВТОРОЙ игрок
В заданиях 19 и 20 выигрышную стратегию ищут для Пети — того, кто ходит первым. Задание 21 переворачивает роль: стратегию нужно построить для Вани, второго игрока. Из-за этого меняется порядок кванторов «существует» / «для любого», а вместе с ним — и вся логика решения.
Стратегия Пети (задание 20) устроена так: Петя один раз выбирает свой первый ход, а дальше должен победить для любого ответа Вани. Формально: « ход Пети такой, что ход Вани Петя выигрывает вторым ходом».
Стратегия Вани (задание 21) устроена наоборот: Ваня не выбирает, с чего начнётся игра, — первый ход уже сделал Петя, и он мог сделать любой из своих ходов. Ваня должен победить, каким бы ни был этот первый ход. Формально: « ход Пети ход Вани такой, что Ваня побеждает». Квантор «для любого» стоит первым и относится к сопернику, а не к самому Ване — это и есть источник дополнительной сложности.
Добавьте к этому, что выигрыш нужно получить не «когда-нибудь потом», а строго в один из двух конкретных моментов — на первом или на втором ходу Вани, — и кванторная конструкция становится трёхэтажной: «для любого хода Пети существует ход Вани, такой что либо игра заканчивается сразу, либо для любого ответного хода Пети существует завершающий ход Вани». Именно эта вложенность кванторов и делает задание 21 заданием высокого уровня, а не технической разницей в арифметике.
Второе условие задания — «у Вани НЕТ стратегии выиграть гарантированно первым ходом» — добавляет проверку в обратную сторону: нужно убедиться, что хотя бы один ответ Пети не даёт Ване закончить игру сразу, иначе задача превращается в задание 19 и берётся не то значение S.
Строгая разметка позиций: П1, В1, П2, В2
Чтобы не путаться в дереве игры, каждой позиции удобно присвоить метку — чей сейчас ход и который он по счёту:
- П1 — начальная позиция, из неё делает свой первый ход Петя.
- В1 — позиция после первого хода Пети, из неё делает свой первый ход Ваня.
- П2 — позиция после первого хода Вани, из неё делает свой второй ход Петя.
- В2 — позиция после второго хода Пети, из неё делает свой второй ход Ваня.
Формальные определения через кванторы
Позиция называется терминальной, если сумма камней в ней уже не меньше порога T. Как только терминальная позиция получена, игра заканчивается и выигрывает тот, кто сделал последний ход, — новых ходов из терминальной позиции не делает никто.
«Ваня выигрывает не позднее чем своим k-м ходом из позиции X» (запишем это как ) определяется рекурсивно:
- истинно, если существует ход Вани из X, ведущий сразу в терминальную позицию (Ваня побеждает немедленно) — тогда k может быть любым, хоть 1;
- иначе, при , истинно, если существует «неторопливый» ход Вани в позицию Y (нетерминальную), такой что для любого ответного хода Пети из Y в позицию Z верно: Z не терминальна (иначе выиграл бы Петя) и истинно;
- во всех остальных случаях ложно.
Условие задания 21 через эту запись выглядит компактно. Обозначим начальную позицию П1 буквой I. Тогда нужное S — то, для которого:
Первая половина — это «у Вани есть стратегия выиграть первым или вторым ходом при любой игре Пети». Вторая половина — это «у Вани нет стратегии выиграть гарантированно первым ходом»: достаточно, чтобы хотя бы один ход Пети не позволял Ване закрыть партию сразу же.
Как построить и прочитать полное дерево игры
Дерево игры строится слой за слоем: корень — позиция П1, дальше каждый слой — все возможные ходы того игрока, чья очередь. Правило построения простое: из каждой позиции проведите по одной ветке на каждый допустимый ход (обычно их две — «+1» и «×2», а если куч несколько, то по два варианта на каждую кучу). Позицию с суммой (или произведением, смотря какое у игры условие окончания) не меньше порога T дальше не разворачивайте — она терминальна, партия в ней уже закончена.
Разберём мини-игру с одной кучей на маленьких числах — правила те же, что и в задании 21, только порог маленький, чтобы дерево уместилось целиком. Порог , в куче камня, ход — «+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. Ваня побеждает.
- Ваня играет «×2» → П2: 8 (не терминал) — альтернатива, показываем для контраста.
- Петя играет «+1» → В2: 9. Ваня завершает: 9×2=18 ≥ 11. Ваня побеждает.
- Петя играет «×2» → 16 ≥ 11 — терминал, и последний ход сделал Петя. Петя побеждает.
- Ваня играет «+1» → П2: 5 (не терминал).
- Петя играет «×2» → В1: 6. Ваня завершает сразу: 6×2=12 ≥ 11. Ваня побеждает первым ходом.
- Петя играет «+1» → В1: 4 (не терминал, Ваня не может закончить: 4+1=5, 4×2=8, оба меньше 11).
Итог по дереву: что бы ни сыграл Петя первым ходом (4 или 6), у Вани находится ответ, гарантирующий победу не позднее второго хода (для 6 — сразу первым ходом, для 4 — вторым ходом через промежуточную позицию 5). При этом не для любого первого хода Пети Ваня выигрывает немедленно — ветка «Петя играет 4» требует второго хода. Значит, S = 3 при T = 11 одновременно удовлетворяет обоим условиям задания 21: выигрыш не позднее второго хода есть, а гарантии выигрыша ровно первым ходом — нет.
| Ход Пети (П1→В1) | Ваня выигрывает немедленно? | Если нет — ход Вани (В1→П2) | Побеждает ли Ваня не позднее 2-го хода? |
|---|---|---|---|
| 3 → 4 | нет | 4 → 5 | да (оба ответа Пети из 5 дают Ване финиш) |
| 3 → 6 | да (6×2=12≥11) | — | да, первым ходом |
Именно так и читается дерево на экзамене: сверху вниз по уровням П1 → В1 → П2 → В2, на каждом уровне держим в уме, чей это ход, и на каждом ходе Пети (уровни П1 и П2) проверяем все его варианты, а на каждом ходе Вани (уровни В1 и П2 → В2) достаточно найти один подходящий.
Python-решатель для всего блока 19–21
Дерево вручную удобно строить только для маленьких порогов. На реальных числах ФИПИ (порог 50–150, две кучи по 4 хода в каждой позиции) дерево разрастается быстро, и его перебирают программой — рекурсией с мемоизацией. Ниже код для игры с двумя кучами и порогом по сумме камней (это самый частый вариант условия); для одной кучи или для порога по произведению меняются только функции и .
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Функция — это прямая запись рекурсивного определения из предыдущего блока: «существует ход, завершающий игру сразу, а если нет — существует ход в нетерминальную позицию, такой что для ЛЮБОГО ответа соперника (сам нетерминальный) удаётся выиграть не позднее следующих ходов». Три конкретных задания блока — это три способа применить одни и те же функции к позиции П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, ) даёт , и — то есть 23 как наименьшее значение для задания 21. Все три числа совпадают с эталонами открытого банка ФИПИ для этого варианта.
Как проверить ответ вручную, не полагаясь только на код
Программа быстро находит число, но на экзамене компьютера с Python не будет — задание 21 всё же решается на черновике рассуждением, а не перебором всех S от 1 до 53. Проверка вручную для конкретного кандидата S строится в три шага.
- Выпишите все ходы Пети из начальной позиции (обычно их четыре: «+1» к каждой куче и «×2» для каждой кучи). Для каждого сразу отбросьте те, что уже завершают игру, — они дают победу Пете и автоматически проваливают всю проверку для этого S.
- Для каждого оставшегося хода Пети проверьте, может ли Ваня закончить партию одним ходом (прибавьте 1 к каждой куче и удвойте каждую кучу — хотя бы один результат должен достичь порога). Если да — эта ветка Пети закрыта на первом ходу Вани, дальше её не разворачивайте.
- Для веток, не закрытых на первом ходу, повторите тот же перебор ещё на один уровень глубже: переберите ходы Вани, а для каждого — ВСЕ ответы Пети, и для каждого такого ответа проверьте, что Ваня снова может закончить партию одним ходом. Если для какого-то хода Вани это верно при любом ответе Пети — ветка закрыта на втором ходу.
Если после этого разбора все ветки Пети закрыты (первым или вторым ходом Вани) — первое условие выполнено. Если хотя бы одна ветка Пети не закрылась на первом ходу Вани — выполнено и второе условие. S, для которого верно и то и другое, и есть решение; если решений несколько, берите наименьшее. На реальных числах ФИПИ полезно сначала прикинуть диапазон S перебором сверху (у больших S Ваня почти всегда выигрывает первым ходом — второе условие не выполняется) и снизу (у маленьких S Петя обычно успевает выиграть сам), а затем сузить поиск до нескольких кандидатов и проверить их руками по описанному алгоритму.
Задание 21 против заданий 19 и 20: не перепутайте условие
| Признак | Задание 19 | Задание 20 | Задание 21 |
|---|---|---|---|
| Чью стратегию ищем | ситуацию для Вани (существование) | Пети | Вани |
| За сколько ходов | 1 ход Вани | ровно 2-й ход Пети | 1-й или 2-й ход Вани |
| Ответ | одно число | два числа в порядке возрастания | одно число |
| Уровень | базовый | повышенный | высокий |
Простое правило: если ищете стратегию Пети — это задание 20; если стратегию Вани и в условии есть слова «первым или вторым ходом» — это задание 21.
Алгоритм решения задания 21
- Прочитайте условие игры в задании 19 — задание 21 своей копии условия не имеет. Выпишите: сколько куч, какие в них начальные числа (в том числе для куда какая связана с S), какой порог и что считается порогом — сумма или произведение.
- Выпишите все возможные ходы из произвольной позиции — обычно «+1» к каждой куче и «×2» для каждой кучи отдельно.
- Для кандидата S постройте позицию П1 и переберите все ходы Пети. Сразу отбросьте S, при котором хотя бы один ход Пети завершает игру, — Петя тогда либо выигрывает сам, либо (что для задания 21 неважно) условие «Ваня выигрывает при любой игре Пети» рушится в этой же ветке.
- Для каждой оставшейся ветки Пети проверьте, есть ли у Вани немедленно завершающий ход. Если да для всех веток — это уже условие задания 19, а не 21: такое S нужно исключить из ответа задания 21 (второе условие требует отсутствия гарантии выигрыша ровно первым ходом).
- Для веток, не закрытых первым ходом, проверьте второй ход: существует ли ход Вани, после которого при любом ответе Пети у Вани находится завершающий ход.
- Проверьте оба условия задания одновременно. Первое: все ветки Пети закрыты не позднее второго хода Вани. Второе: хотя бы одна ветка не закрылась уже на первом ходу.
- Переберите S от меньших к большим (или наоборот, если выгоднее) и возьмите наименьшее подходящее. Запишите в ответ одно целое число без пробелов и разделителей.
Доведите разбор игры до автоматизма
Прорешайте несколько вариантов подряд — и структура «для любого хода Пети существует ход Вани» перестанет пугать. Задания 21 ЕГЭ по информатике из банка ФИПИ — на Repet.ai.
Примеры с разбором
Пример 1. Две кучи, порог по сумме
Условие (реальное задание из открытого банка ФИПИ):
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было пять камней, во второй куче – S камней; . Для игры, описанной выше, найдите минимальное значение S, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.»
Решение:
Позиция задаётся парой (первая куча, вторая куча) = (5, S), порог суммы — 59. Проверим кандидата S = 23: начальная позиция (5, 23), сумма 28.
Ходы Пети из (5, 23): (6, 23), (5, 24), (10, 23), (5, 46) — суммы 29, 29, 33, 51, все меньше 59, Петя выиграть за один ход не может ни при каком выборе.
Петя: (5,23)→(6,23), сумма 29 — Ваня финишем сразу не закрывает
Ваня играет (12,23), сумма 35:
Петя: (13,23)=36, (12,24)=36, (24,23)=47, (12,46)=58
из каждой позиции у Вани находится завершающий ход (например,
из (12,46) — ×2 второй кучи: 12+92=104 ≥ 59)
Все четыре ответа Пети закрыты — ветка рабочая, Ваня выигрывает вторым ходом.
Петя: (5,23)→(5,24), сумма 29 — Ваня финишем сразу не закрывает
Ваня играет (10,24), сумма 34:
Петя: (11,24)=35, (10,25)=35, (20,24)=44, (10,48)=58
из каждой позиции у Вани находится завершающий ход (например,
из (10,48) — +1 к первой куче: 11+48=59 ≥ 59)
Ветка рабочая.
Петя: (5,23)→(10,23), сумма 33 — Ваня финишем сразу не закрывает
Ваня играет (10,24), сумма 34 (тот же ход, что и в предыдущей ветке):
Петя: (11,24)=35, (10,25)=35, (20,24)=44, (10,48)=58 — все закрыты
Ветка рабочая.
Петя: (5,23)→(5,46), сумма 51
Ваня: (6,46)=52, (5,47)=52, (10,46)=56, (5,92)=97 ≥ 59 — финиш есть сразу!
Ваня побеждает первым ходом, удвоив вторую кучу.Все четыре хода Пети закрыты не позднее второго хода Вани — первое условие задания выполнено. При этом три из четырёх веток (6,23), (5,24) и (10,23) на первом ходу Вани финиша не дают: ни один из ходов Вани из этих позиций сразу не достигает 59. Значит, гарантии закрыть партию ровно первым ходом при любом ходе Пети у Вани нет — второе условие тоже выполнено.
Заметьте характерную ловушку на ветке (10,23): Ваня может сыграть и (10,46), сумма 56, но тогда среди ответов Пети найдутся (20,46)=66 и (10,92)=102 — оба уже ≥ 59, то есть Петя заканчивает игру сам, раньше Вани. Такой ход Вани не годится, а рабочий — именно (10,24). Программа-решатель перебирает все варианты и не совершает эту ошибку, ручной разбор — совершает её постоянно.
Ответ: 23. Проверка здравым смыслом: при S = 22 (на единицу меньше) хотя бы одна ветка Пети — например, (6, 22) — уже не закрывается у Вани ни первым, ни вторым ходом ни при одном из ответных ходов Вани, то есть первое условие задания перестаёт выполняться. 23 — действительно наименьшее подходящее значение.
Пример 2. Одна куча
Условие (реальное задание из открытого банка ФИПИ):
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень либо увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход. В начальный момент в куче было S камней, . Для игры, описанной выше, найдите значение S, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Если найдено несколько значений S, в ответе запишите минимальное из них.»
Решение:
Здесь куча одна, порог — 29, и удобно проверять S от меньших к большим. Возьмём S = 12: ходы Пети из 12 — это 13 («+1») и 24 («×2»), обе позиции меньше 29, выиграть за один ход Петя не может.
Петя: 12 → 13
Ваня: 13+1=14, 13×2=26 — оба меньше 29, финиша нет.
Ваня играет 13 → 14 (пробуем этот второй уровень):
Петя: 14+1=15, 14×2=28 — оба меньше 29
Ваня из 15: 15+1=16, 15×2=30 ≥ 29 — финиш есть
Ваня из 28: 28+1=29 ≥ 29 — финиш есть
При любом ответе Пети из 14 у Вани находится завершающий ход — ветка рабочая.
Петя: 12 → 24
Ваня: 24+1=25, 24×2=48 ≥ 29 — финиш есть сразу!
Ваня побеждает первым ходом.Обе ветки Пети закрыты: (12→13) — вторым ходом Вани через промежуточное значение 14, (12→24) — первым же ходом. Первое условие выполнено. При этом ветка (12→13) не закрывается первым ходом Вани (14 и 26 оба меньше 29) — значит, гарантии выиграть ровно первым ходом при любом ходе Пети у Вани нет. Второе условие тоже выполнено.
Ответ: 12. В этом варианте условию удовлетворяет только одно значение S, поэтому оговорка «если найдено несколько — берите наименьшее» здесь не понадобилась, но её всё равно нужно перепроверять при каждом S: пропуск этой фразы — частая причина ошибки на похожих вариантах.
Пример 3. Порог по произведению камней
Условие (реальное задание из открытого банка ФИПИ):
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. За один ход игрок может добавить в одну из куч один камень либо увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда произведение количеств камней в кучах становится не менее 144. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было два камня, во второй куче — S камней; . Для игры, описанной выше, найдите минимальное значение S, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.»
Решение:
Условие завершения игры здесь другое — не сумма, а произведение камней в кучах не менее 144. Меняется только функция проверки терминальности, вся логика дерева остаётся такой же. Проверим S = 22: позиция (2, 22), произведение 44.
Петя: (2,22) → (3,22)=66, (2,23)=46, (4,22)=88, (2,44)=88 — все < 144
Ветка (3,22), произведение 66. У Вани нет хода, сразу дающего 144:
(4,22)=88, (3,23)=69, (6,22)=132, (3,44)=132 — всё меньше 144.
Ваня играет (6,22)=132 — выглядит агрессивно (кучу удвоили):
Петя отвечает (7,22)=154 ≥ 144 — Петя выигрывает сам! Ход не годится.
Ваня играет (3,44)=132 — тоже удвоение:
Петя отвечает (4,44)=176 ≥ 144 — снова плохо.
Ваня играет (3,23)=69 — скромное «+1» к первой куче:
Петя: (4,23)=92, (3,24)=72, (6,23)=138, (3,46)=138
из каждой позиции Ваня находит завершающий ход (например,
из (6,23) — ×2 второй кучи: 6×46=276 ≥ 144)
Ветка (3,22) закрыта вторым ходом Вани через (3,23).
Ветка (2,23), произведение 46. Тем же ходом «+1» к первой куче Ваня
получает ту же позицию (3,23)=69, и она снова закрывает партию не
позднее второго хода — доказательство дословно повторяет ветку (3,22).
Ветка (4,22), произведение 88. Ваня финиширует СРАЗУ:
(5,22)=110, (4,23)=92, (8,22)=176≥144, (4,44)=176≥144 — финиш есть.
Ваня побеждает первым ходом, удвоив любую из куч.
Ветка (2,44), произведение 88. Ваня тоже финиширует СРАЗУ:
(3,44)=132, (2,45)=90, (4,44)=176≥144, (2,88)=176≥144 — финиш есть.
Ваня побеждает первым ходом.Обратите внимание: из четырёх ходов Пети два ((4,22) и (2,44)) Ваня закрывает уже первым ходом, а два ((3,22) и (2,23)) — только вторым, через один и тот же промежуточный ход (3,23). Значит, гарантии выиграть ровно первым ходом при любом ходе Пети у Вани нет — ветки (3,22) и (2,23) требуют второго хода. Оба условия задания 21 выполнены.
Ответ: 22. Проверка здравым смыслом: 22 — наименьшее из двух значений, которые даёт полный перебор для этого варианта (второе, большее значение — 33, тоже удовлетворяет обоим условиям, но в ответ идёт меньшее).
Типичные ошибки
Путаница «Петя выигрывает» и «Ваня выигрывает»
Задания 19 и 20 ищут ситуацию/стратегию для Пети (первого игрока), задание 21 — для Вани (второго). Легко машинально продолжить логику предыдущего задания и искать «для Пети существует ход» вместо «для любого хода Пети существует ход Вани». Перед решением явно выпишите на черновике, чья стратегия нужна именно в этом задании.
Забыть отсечь S, где Ваня выигрывает уже первым ходом
Условие задания 21 требует, чтобы гарантии выиграть ровно первым ходом у Вани НЕ было. Если проверять только первое условие (выигрыш не позднее второго хода) и забыть про второе, в ответ попадут значения S, которые на самом деле относятся к заданию 19 или к более простому случаю — и решение засчитают неверным.
Неверная база рекурсии: не проверять терминальность хода СОПЕРНИКА
Проверяя ветку Вани, легко забыть, что каждый ответный ход Пети тоже может сразу завершить игру в его пользу — как в примерах выше с (20,46) и (7,22). Прежде чем спрашивать «может ли Ваня закрыть партию из этой позиции», сначала проверьте: а не закрыл ли её только что сам Петя. Пропуск этой проверки — самая частая причина неверного ответа в этом задании.
Выбрать первый «подходящий на вид» ход Вани вместо проверки всех ответов Пети
Удвоение кучи выглядит «самым сильным» ходом, но именно оно часто подпускает Петю к победе за один шаг (см. ветку (3,22) в примере 3, где удвоение проигрывает, а скромное «+1» — выигрывает). Ход Вани годится только тогда, когда он выдерживает все четыре ответа Пети, а не один-два самых очевидных.
Перепутать условие окончания игры — сумма или произведение
В части вариантов игра заканчивается по сумме камней в кучах, в части — по произведению. Формулы дерева не меняются, но функция проверки терминальности — да. Одна и та же позиция (4, 22) при пороге по сумме 59 не терминальна, а при пороге по произведению 144 — тоже не терминальна, но уже соседняя (8, 22) при произведении даёт 176 ≥ 144. Перед началом решения перечитайте, что именно должно стать «не менее X»: сумма или произведение.
Забыть про вторую кучу и её начальное значение
Условие игры (в задании 19) обычно указывает, что в первой куче лежит фиксированное число камней, а переменная S относится ко второй. При построении позиций легко перепутать местами, к какой куче прибавляется S, — тогда все дальнейшие вычисления окажутся верными по логике, но неверными по числам.
Не заметить фразу «если найдено несколько значений S»
Условиям задания 21 нередко удовлетворяет не одно, а несколько значений S (в примере 1 — это 23 и 25, в примере 3 — 22 и 33). В ответ нужно записывать наименьшее. Нашли одно подходящее значение — не останавливайтесь, продолжайте перебор дальше хотя бы ещё на несколько S, чтобы убедиться, что меньшего решения не пропущено.
Как задание 21 связано с остальным экзаменом
- Задание 19 — то же условие игры целиком, вопрос про существование ситуации «Ваня выиграл первым ходом после неудачного хода Пети», базовый уровень.
- Задание 20 — то же условие, но стратегия ищется для Пети и должна сработать ровно на его втором ходу, повышенный уровень, ответ — два числа.
- Задания 19–21 — единственный блок КЕГЭ с общим условием; во всех остальных 24 заданиях условие уникально для каждого задания.
- Оба соседних задания и задание 21 проверяют один и тот же раздел кодификатора — «Теоретические основы информатики» / КЭС 2.15 — но с разной глубиной анализа дерева игры: 19 требует посмотреть на один уровень вперёд, 20 и 21 — на два.
План подготовки
Неделя 1: язык игр и заданий 19–20
Начните с заданий 19 и 20 — они проще и вводят тот же аппарат (ходы, терминальная позиция, «выигрышная стратегия»). Прорешайте 10–15 вариантов 19-го и 20-го заданий, каждый раз явно выписывая все ходы из начальной позиции. Это закладывает базу для 21-го.
Неделя 2: дерево игры и позиции П1/В1/П2/В2
Возьмите 5–7 заданий 21-го типа и для каждого стройте дерево руками на черновике: явно подписывайте у каждого узла метку (П1, В1, П2, В2) и сумму (или произведение). После каждого разбора сверяйте свой ответ с python-решателем из этой статьи — расхождение почти всегда означает пропущенную ветку или неучтённый мгновенный выигрыш соперника.
Неделя 3: скорость и оба варианта условия
Отрабатывайте задания с условием и по сумме, и по произведению камней — они попадаются в банке примерно поровну. Засекайте время: цель — укладываться в 11 минут, отведённые ФИПИ на это задание, оставляя запас на остальные 26 заданий работы.
Неделя 4: смешанный блок 19–21 и пробный экзамен
Решайте задания 19, 20 и 21 подряд для одного и того же варианта — так вы научитесь удерживать в голове общее условие и не путать, какая стратегия и для кого именно нужна в каждом из трёх заданий. Завершите подготовку пробным экзаменом КЕГЭ целиком, чтобы увидеть задание 21 в контексте всей работы.
Проверьте себя на реальных вариантах
Задания 21 ЕГЭ по информатике из открытого банка ФИПИ с мгновенной проверкой ответа — бесплатно на Repet.ai.
Часто задаваемые вопросы
Задание 21 — часть блока 19-21 с общим условием игры про камни в кучах. Оно проверяет умение построить полное дерево игры и найти минимальное значение параметра S, при котором у второго игрока (Вани) есть выигрышная стратегия, позволяющая ему победить первым или вторым ходом при любой игре первого игрока (Пети), но нет стратегии, гарантирующей выигрыш ровно первым ходом. Уровень сложности — высокий, код требования 2.1, КЭС 2.15, за верный ответ дают 1 первичный балл.
В заданиях 19 и 20 стратегия ищется для Пети — игрока, который ходит первым и сам выбирает начальный ход. В задании 21 стратегию нужно построить для Вани, второго игрока: он вынужден реагировать на любой из возможных ходов Пети. Порядок кванторов меняется на 'для любого хода Пети существует ход Вани', а сам выигрыш дополнительно ограничен рамками первого или второго хода Вани — такая вложенность условий и относит задание к высокому уровню сложности.
Задание 21 не содержит собственного условия игры: оно начинается словами 'Для игры, описанной выше...' и ссылается на текст задания 19 того же варианта. Прежде чем решать 21-е задание, обязательно прочитайте условие в задании 19 — там указаны число куч, начальные значения и порог окончания игры.
В части вариантов игра заканчивается, когда сумма камней в кучах достигает порога T, в части — когда порога достигает произведение количеств камней. Правила ходов и вся логика построения дерева при этом не меняются, меняется только проверка 'позиция уже терминальна или ещё нет'. Перед решением важно точно определить, какое условие используется в конкретном варианте.
Постройте дерево вручную: из начальной позиции переберите все ходы Пети, для каждого проверьте, может ли Ваня закончить партию одним ходом, а для оставшихся веток — постройте ещё один уровень (ход Вани, затем все ответы Пети, затем финальный ход Вани). Кандидат S подходит, если все ветки Пети закрыты не позднее второго хода Вани, но хотя бы одна ветка не закрывается уже первым ходом.
Нет: ЕГЭ по информатике сдаётся на компьютере, но интернет и заранее принесённые программы недоступны — код нужно писать в среде программирования во время экзамена, и тратить на это 11 минут, отведённых на задание 21, нерационально. Python-решатель полезен при подготовке дома, чтобы проверять свои ручные разборы, а на экзамене эффективнее решать деревом на черновике.
Забыть проверить, не заканчивает ли игру сам ответный ход Пети. При разборе дерева легко проверить только то, может ли Ваня закончить партию из очередной позиции, и упустить, что один из ходов Пети в эту позицию уже сам достигает порога — тогда выигрывает Петя, а не Ваня, и вся ветка становится непригодной.
По обобщённому плану варианта КИМ (спецификация ЕГЭ по информатике 2026 года) на задание 21 отводится примерно 11 минут — больше, чем на любое другое задание из первой половины работы, что отражает трудоёмкость построения двухуровневого дерева игры.