Статья Автор: Деникина Н.В., Деникин А.В.

Теория игр. Рекурсивное решение

Подготовка к ЕГЭ · ИнформатикаЗадание 19-21

SilverTests.ru · УчебникТеория игр: рекурсивный шаблон

Теория игр. рекурсивное решение

Рекурсивный шаблон для задач 19–21 ЕГЭ: одна куча, две кучи, нестандартные условия

🎯 Чему научимся

Разберём универсальный рекурсивный шаблон для задач 19–21 ЕГЭ по информатике. Поймём, как работают функции W и L (выигрыш/проигрыш за k ходов), почему на разных уровнях рекурсии нужно чередовать any и all, и как адаптировать шаблон, когда условия победы нестандартны — например, зависят от чётности итогового количества камней.

1О задачах 19–21

Три задания ЕГЭ под общим условием. Два игрока по очереди делают ходы с кучей (или двумя кучами) камней. Игра кончается при достижении порога. Три стандартных вопроса:

Задание 19

Простейший вопрос: при каких S игрок (обычно Петя) выигрывает первым ходом. Ответ ищется прямым перебором трёх-четырёх возможных ходов — без рекурсии.

Задание 20

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

Задание 21

Теперь побеждает Ваня. У него есть стратегия выиграть за 1 или 2 своих хода при любой игре Пети, но не гарантированно первым. Рекурсия на 3–4 уровня.

На первый взгляд задачи совершенно разные. На самом деле все три решаются одной функцией, которой меняешь параметры. Это и есть главный приём.

2Ключевая идея: any и all

Всё сводится к одному наблюдению. Когда ходит наш игрок, он выбирает лучший ход — достаточно, чтобы существовал выигрышный вариант. Это any.

Когда ходит соперник, он играет оптимально против нас. Чтобы наша стратегия работала, она должна побеждать при любом его ходе. Это all.

Базовое правило: наш ход — any; ход соперника — all. Всё остальное в задачах теории игр — технические детали вокруг этого правила.

Чередование хода кодируется через параметр n: номер хода с начала игры. Если n чётное — сейчас ход того, кто начал (обычно Петя); если нечётное — второго игрока (Ваня). А уровень рекурсии заодно служит ограничением глубины: можно легко ответить на вопрос «за сколько ходов выиграет».

3Задача про одну кучу: демо-стиль

Начнём с классической простой задачи. Куча камней. Петя ходит первым. За ход можно добавить один камень или удвоить кучу. Игра кончается при 30 или более камнях. Побеждает сделавший последний ход.

Для начала найдём рекурсивно: при каком S Петя выигрывает, сделав ход? То есть разберёмся, какие позиции являются «выигрышными» для того, кто в них ходит.

Рекурсивное дерево: кто побеждает при 13 камнях?

Меняй начальное число камней и смотри, как разворачивается рекурсия. Зелёный узел — ходящий из него игрок победит. Красный — проиграет. Одна куча, ходы: +1 или ×2, порог 30.

Ходящий из S=13: посмотри на корень. Зелёный — побеждает; красный — проигрывает.

В дереве видно главное: позиция выигрышна для ходящего, если есть хотя бы один ход в проигрышную позицию для соперника. Позиция проигрышна, если все ходы ведут в выигрышные позиции соперника. Это и есть то самое чередование any/all.

4Универсальная функция f(s, n)

Запишем рекурсию в коде. Параметр n — номер хода (0, 1, 2…). Мы проверяем: побеждает ли Петя (первый игрок) из позиции s на ходу n?

Код шаблона (Python)

1def f(s, n=0):

2 # конец игры: куча достигла порога

3 if s >= 30:

4 # n ходов сделано; последним ходил n-1-й игрок

5 # если n нечётное — ходил Петя (и победил)

6 return n % 2 == 1

8 # обрезка по глубине (для вопросов про k ходов)

9 if n >= 4:

10 return False

12 # рекурсия по всем ходам

13 results = [f(s+1, n+1), f(s*2, n+1)]

15 if n % 2 == 0:

16 return any(results) # ход Пети: хочет победы

17 else:

18 return all(results) # ход Вани: он против нас

20# проверка: для каких S из 1..29 Петя побеждает?

21for s in range(1, 30):

22 if f(s):

23 print(s, '— Петя')

стр 6 — n % 2 == 1: если после нечётного числа ходов куча переполнилась, то последним ходил Петя (ходы 1, 3, 5… — его), значит он победил.

стр 9 — обрезка n >= 4: мы не хотим смотреть дальше двух наших ходов. Это параметр задачи: «выиграть за k ходов».

стр 15–18 — главная развилка: на чётном ходу any (Петя выбирает лучшее), на нечётном — all (Ваня мешает).

Этот маленький шаблон с одной функцией и парой строк условий решает почти все стандартные задачи ЕГЭ на одну кучу. Меняешь порог, меняешь список ходов, меняешь глубину — и получаешь нужный ответ.

5Шаблон для двух куч (демо 2026)

В демоверсии ЕГЭ-2026 задача сформулирована про две кучи. Петя и Ваня ходят по очереди. За ход можно добавить один камень в любую кучу или удвоить любую кучу. Игра кончается, когда сумма обеих куч достигает 59. Побеждает сделавший последний ход. В первой куче 5 камней, во второй — S камней, 1 ≤ S ≤ 53.

Задание 19

При каких S Петя выигрывает первым ходом? Удвоение: 5 + 2S ≥ 59 даёт S ≥ 27. Другие ходы: 10 + S ≥ 59 даёт S ≥ 49; +1 даёт порог S ≥ 53. Самое маленькое — S = 27.

Задание 20

Петя не может выиграть 1-м ходом, но имеет стратегию выиграть 2-м при любой игре Вани. Ответ: S = 24 и 26.

Задание 21

Ваня выигрывает первым или вторым своим ходом при любой игре Пети, но не гарантированно первым. Ответ: S = 23 и 25.

Шаблон почти такой же, только позиция — это пара (s1, s2), и ходов теперь четыре.

Главный трюк: одна функция f решает все три задания. Меняется только параметр limit (глубина рекурсии) и условие в main. Писать три разные функции для трёх заданий — лишняя работа.

Единый код для заданий 19–21 (Python)

1def moves(s1, s2):

2 return [(s1+1,s2), (s1,s2+1), (s1*2,s2), (s1,s2*2)]

4def f(s1, s2, n=0, limit=4):

5 # побеждает ли Петя из позиции (s1, s2) на ходу n?

6 if s1 + s2 >= 59:

7 return n % 2 == 1 # нечёт n → последним ходил Петя

8 if n >= limit:

9 return False # не успел победить за limit ходов

10 results = [f(a, b, n+1, limit) for a, b in moves(s1, s2)]

11 return any(results) if n % 2 == 0 else all(results)

13def g(s1, s2, n=0, limit=4):

14 # побеждает ли Ваня (та же логика, но против нас играет Петя)

15 if s1 + s2 >= 59:

16 return n % 2 == 0 and n > 0 # чёт n>0 → ходил Ваня

17 if n >= limit:

18 return False

19 results = [g(a, b, n+1, limit) for a, b in moves(s1, s2)]

20 # чётное n — ход Пети (мешает), all

21 return all(results) if n % 2 == 0 else any(results)

23# ==== ответы на три задания ====

25print('Задание 19:', min(s for s in range(1, 54)

26 if f(5, s, 0, 1)))

28print('Задание 20:', [s for s in range(1, 54)

29 if not f(5, s, 0, 1) and f(5, s, 0, 3)])

31print('Задание 21:', [s for s in range(1, 54)

32 if g(5, s, 0, 4) and not g(5, s, 0, 2)])

стр 4–11 — функция f «от лица Пети»: возвращает, побеждает ли Петя. Параметр limit — сколько всего полуходов разрешено сделать.

стр 7 — терминальное условие. n % 2 == 1 значит: было нечётное число полуходов, то есть последним ходил Петя (он играет на ходах 0, 2, 4… в терминах 0-индексации, а именно на ходах с номером 1, 3, 5… в «человеческой» нумерации).

стр 11 — чередование: any когда ходит наш игрок (Петя), all когда ходит соперник.

стр 13–21 — функция g «от лица Вани». Отличия минимальны: терминал проверяет чёт n (ходил Ваня), и местами меняются any/all.

стр 26 — f(5, s, 0, 1): limit=1 — рассматриваем только первый ход Пети. Если он сразу достигает порога — задание 19 решено.

стр 29 — not f(..., 1) and f(..., 3): Петя не выигрывает за 1 полуход, но выигрывает за 3 (Петя—Ваня—Петя), что и есть «победа 2-м ходом».

стр 32 — g(..., 4) and not g(..., 2): Ваня выигрывает за ≤4 полуходов (т.е. за 2 своих), но не за ≤2 полуходов (не за 1 свой).

На вид длинно, но функции f и g — почти близнецы. Отличаются всего двумя вещами: проверкой чётности в терминале и порядком any/all. Сейчас разберёмся, как сжать их в одну.

От двух функций к одной: путь рассуждения

Будем двигаться постепенно. Цель — получить функцию, в которой нет привязки к «Пете» или «Ване». Для этого введём хитрое обозначение.

Шаг 1. Параметр m вместо n. Вместо того чтобы считать номер хода от начала (n = 0, 1, 2, …), будем считать наоборот: сколько полуходов ещё разрешено. Сверху передаём M (максимальное число полуходов), и с каждым вызовом m уменьшается на единицу. Когда m = 0 — рекурсия останавливается.

Почему это удобно? Ответ на задание типа «Петя выигрывает за 2 своих хода» сводится к простой подстановке M = 3 (3 полухода = Петя—Ваня—Петя). Никаких limit с n >= limit.

Шаг 2. Кто такой «целевой игрок»? Функция, вызванная сверху как f(..., M), отвечает на вопрос: «сможет ли игрок, который сделает М-й ход, победить?».

M = 1: 1-й ход. Делает Петя. Вопрос: может ли Петя победить своим первым ходом? — задание 19.
M = 2: 2-й ход. Делает Ваня. Может ли Ваня гарантированно дойти до победы 1-м своим ходом? — задание 19 в другой формулировке.
M = 3: 3-й ход. Делает Петя (1-й → 2-й → 3-й). Может ли Петя гарантированно победить 2-м своим ходом? — задание 20.
M = 4: Ваня 2-м своим ходом — задание 21.

Одна функция — четыре разных вопроса. Красота.

Шаг 3. Что возвращать в терминале. Допустим, вызвали f(..., M), и после нескольких полуходов мы добрались до s1 + s2 ≥ 59. Последним ходил тот, кто сделал этот самый дошедший до порога ход — и он победил (стандартное правило).

Сколько ходов он сделал? Если мы начали с M и сейчас m оставшихся, то сделано M - m. Последним ходил игрок на позиции M - m. А «целевой» игрок у нас — на позиции M.

Вопрос: победил ли целевой? Да, если позиция последнего хода «той же чётности», что и M. То есть:

целевой победил ⟺ (M - m) % 2 == M % 2 ⟺ m % 2 == 0

Шикарно: M в формуле сократился! Не нужно знать, с чем нас вызвали сверху — чётность m в терминале сама знает ответ.

Шаг 4. Чередование any/all через m. В теле рекурсии нужно понимать: сейчас ход «нашего» игрока (M-го) или соперника?

Сейчас ходит игрок на позиции (M - m) + 1 = M - m + 1. «Наш» — на позиции M. Это один и тот же игрок, когда (M - m + 1) и M одной чётности, то есть (m - 1) чётно. Итого:

сейчас ход «нашего» (применяем any) ⟺ (m - 1) % 2 == 0

Вот откуда взялось (m - 1) % 2 == 0 в рекурсии! Опять же, M в формуле сократился.

Шаг 5. Собираем всё вместе.

Короткий вариант — 9 строк функции

1def f(s1, s2, m):

2 if s1 + s2 >= 59:

3 return m % 2 == 0 # целевой игрок победил?

4 if m == 0:

5 return 0 # ходы кончились, не успели

6 moves = [f(s1+1, s2, m-1), f(s1, s2+1, m-1),

7 f(s1*2, s2, m-1), f(s1, s2*2, m-1)]

8 if (m - 1) % 2 == 0: return any(moves) # наш ход

9 else: return all(moves) # ход соперника

11print('Задание 19:', min(s for s in range(1, 54) if f(5, s, 1)))

12print('Задание 20:', [s for s in range(1, 54) if not f(5, s, 1) and f(5, s, 3)])

13print('Задание 21:', [s for s in range(1, 54) if not f(5, s, 2) and f(5, s, 4)])

Проверяем на примере

Разберём f(5, 27, 1) — задание 19, S=27. Вызов сверху с M = 1: спрашиваем «победит ли Петя 1-м своим ходом?».

Проверяем ходы: (6, 27), (5, 28), (10, 27), (5, 54). Последний даёт сумму 59 — порог достигнут.
Внутри f(5, 54, 0): s1 + s2 = 59 ≥ 59, возвращаем 0 % 2 == 0 = True.
В рекурсии: (m - 1) % 2 = 0, значит any. Хоть один True есть — возвращаем True.

Ответ: при S = 27 Петя побеждает 1-м ходом. Это минимальное такое S — ответ на задание 19.

Теперь f(5, 23, 4) — задание 21, S=23. M = 4 значит «целевой» = 4-й по порядку = Ваня (2-м своим ходом). Рекурсия разворачивается на 4 уровня вниз. В терминале, если ход № 4 достиг порога — m = 0, 0 % 2 == 0 = True, Ваня победил. В промежуточных вызовах any/all чередуются автоматически. Результат — True.

Главная мысль. Короткий шаблон работает, потому что мы заменили нумерацию от начала на отсчёт до конца. В такой нумерации M из формул сокращается, и остаются только операции с m. Это математический фокус — и он даёт практический выигрыш: код в 2 раза короче, и главное — одна функция решает сразу все 4 вопроса.

6Модификации шаблона под разные условия

Короткий шаблон универсальный — меняются только три вещи: набор ходов, терминальная проверка и способ комбинирования вызовов под заданный вопрос. Вот сводная таблица модификаций.

Что меняется в задаче	Где поправить	Как
Другие ходы (+2, ×3 и т.п.)	Список `moves` в рекурсии	Просто замените выражения: например, `[f(s+2, m-1), f(s*3, m-1)]`
Две кучи вместо одной	Аргументы функции и список ходов	Добавьте второй параметр, в `moves` четыре варианта
Другой порог	Условие `s >= target`	Замените число
Стандартное правило (побеждает последний ход)	Терминал	`return m % 2 == 0`
Побеждает чётность итога (наша задача)	Терминал	`return s % 2 != m % 2`
Задание 19 (мин S, Петя 1-м ходом)	Вызов	`min(s for s ... if f(s, 1))`
Задание 19 в формулировке «Петя проигрывает первым ходом Вани»	Вызов	`not f(s, 1) and f(s, 2)`
Задание 19 «неудачный ход Пети» (сущ. плохой ход)	Вызов	`any(f(x, 1) for x in ходы Пети)`
Задание 20 (Петя за 2, не за 1)	Вызов	`not f(s, 1) and f(s, 3)`
Задание 21 (Ваня за 2, не за 1)	Вызов	`not f(s, 2) and f(s, 4)`

Всё остальное в коде не меняется. Это и есть сила правильного шаблона — одну функцию пишут один раз, а потом 10 лет используют.

Откуда формула s % 2 != m % 2 для задач с чётностью

Короткое объяснение. В обычной задаче победил тот, кто сделал последний ход. Там m % 2 == 0 — это условие «М-й игрок сделал последний ход».

В задаче с чётностью правило двойное: победил сделавший последний ход, если куча нечёт, иначе — его противник. Значит М-й игрок победил в двух случаях:

М-й сделал последний ход (т.е. m нечёт) И куча нечёт — он выиграл своим ходом;
М-й НЕ ходил последним (т.е. m чёт) И куча чёт — его противник подставился.

Объединяя: М-й победил ⟺ чётность s противоположна чётности m. Это и записывается как s % 2 != m % 2. Вся «самоубийственность» хода в чёт-порог автоматически учитывается — не нужно отдельно проверять!

7Главные грабли

Грабля 1. any вместо all

Самая частая ошибка — написать any на обоих уровнях. Тогда задача превращается в «существует ли путь к победе», что нам не подходит: нам нужна гарантированная стратегия, работающая против любого соперника.

Грабля 2. Забыть обрезку по глубине

Без if n >= K рекурсия может уходить глубоко и давать не тот ответ. Если задание спрашивает «за 2 хода» — ставь лимит ровно столько, сколько надо.

Грабля 3. Перепутать чётность n

Если первым ходит Петя (обычно так и есть), то на нулевом ходу ходит Петя (n=0, чётно). После Петиного хода n=1 (нечётное) — ход Вани. А в терминальной проверке — всё наоборот: если на входе рекурсии n=1, то последним ходил тот, у кого был ход 0, то есть Петя.

8Нестандартная задача: чётность итога

Теперь — задача, которая ломает привычный шаблон. Условие:

Два игрока, Петя и Ваня. Одна куча. Первый ходит Петя. За ход можно добавить 1 или 4 камня либо удвоить кучу. Игра кончается, когда в куче становится не менее 35 камней. Если получилось нечётное число — победил сделавший последний ход. Если чётное — победил его противник («считается, что противник сделал свой ход»).

В начальный момент 1 ≤ S ≤ 34.

Ключевая сложность — условие победы не просто «кто последним ходил», а зависит от чётности итогового количества камней. Это всё меняет: теперь ход, приводящий к чёт-куче ≥ 35, самоубийственный — ходивший сразу проигрывает.

Вопросы тоже нестандартные:

Вопрос 1. Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Минимальное S?
Вопрос 2. Петя не выигрывает за 1 ход, но выигрывает за 2 — при любой игре Вани. Минимальное и максимальное S.
Вопрос 3. Ваня выигрывает за 1 или 2 хода при любой игре Пети, но не гарантированно первым. Минимальное S.

Решаем тем же коротким шаблоном — меняется только одна строчка (терминал).

9Применяем короткий шаблон

Берём тот же короткий шаблон, что и в демо 2026. Меняем три вещи:

Порог: было ≥ 59, стало ≥ 35.
Ходы: было +1 и ×2 (две кучи), стало +1, +4, ×2 (одна куча).
Терминал: было m % 2 == 0 (стандартное правило), стало s % 2 != m % 2 (чётность итога).

Весь код (Python)

1def f(s, m):

2 if s >= 35:

3 return s % 2 != m % 2 # ← единственное отличие

4 if m == 0:

5 return 0

6 moves = [f(s+1, m-1), f(s+4, m-1), f(s*2, m-1)]

7 if (m - 1) % 2 == 0: return any(moves)

8 else: return all(moves)

10# Вопрос 1: существует ход Пети, после которого Ваня побеждает 1-м своим

11print('Вопрос 1:', min(s for s in range(1, 35)

12 if any(f(x, 1) for x in [s+1, s+4, s*2])))

14# Вопрос 2: Петя за 2 своих хода, не за 1

15v2 = [s for s in range(1, 35) if not f(s, 1) and f(s, 3)]

16print('Вопрос 2:', min(v2), max(v2))

18# Вопрос 3: Ваня за 2 своих хода, не за 1

19v3 = [s for s in range(1, 35) if not f(s, 2) and f(s, 4)]

20print('Вопрос 3:', min(v3))

стр 3 — единственная строчка, отличающая нашу задачу от стандартной. Всё остальное — тот же шаблон.

стр 12 — вопрос 1 в нестандартной формулировке: существует ход Пети, после которого Ваня выигрывает 1-м своим. Это any по ходам Пети, а дальше f(x, 1) — стандартный вопрос для Вани из позиции x.

стр 15, 19 — задания 20/21 совершенно такие же, как в демо 2026. Только формула терминала другая.

Результат: вся нестандартная задача решилась одной строчкой изменений в шаблоне. Это и есть сила правильной модели: увидел новое условие → изменил одну строчку → получил ответ.

10Разбор по шагам

Что происходит в этой задаче при разных S. Сначала посмотрим на таблицу — для каждого S от 1 до 34 определим статус: Вk — Петя (ходящий первым) выигрывает за k ходов, Пk — проигрывает (Ваня выигрывает за k).

Таблица позиций

Зелёный — Петя побеждает; красный — Ваня. Число рядом — минимум своих ходов до победы.

Например, S=25 (ответ на В3) — красная клетка «П2»: Ваня гарантированно выигрывает за 2 свои хода. А S=15 (В2 min) — зелёная «В2».

Разбор S = 17 (ответ на В1)

Ходы Пети: 17 → 18, 21, 34.

Ход 17 → 18: Ваня в позиции 18. Его ходы: 19, 22, 36. 36 чёт ≥ 35 — Ваня проиграл. 19 и 22 меньше 35. Ваня не выиграет 1-м ходом.
Ход 17 → 21: аналогично, Ваня не побеждает ходом.
Ход 17 → 34 — неудачный! Из 34 Ваня: +1 → 35 (нечёт) — Ваня победил первым ходом.

Значит 17 — первое S, где Петя может сыграть плохо и подарить Ване победу. При меньшем S такого хода нет. Ответ на В1: 17.

Разбор S = 15 (В2 min)

Ходы Пети: 15 → 16, 19, 30. Ключевой ход — ×2 → 30. Посмотрим, что может Ваня из 30.

30 → 31: Петя делает +4 → 35 (нечёт), побеждает.
30 → 34: Петя делает +1 → 35, побеждает.
30 → 60: Ваня сделал чёт ≥ 35, сам подставился. Петя победил без хода.

Любой ход Вани из 30 ведёт к победе Пети следующим ходом. Значит Петя гарантированно выигрывает 2-м ходом: ходит ×2 → 30 и ждёт финала. Ответ на В2 min: 15.

Разбор S = 25 (В3)

Ходы Пети: 25 → 26, 29, 50.

25 → 50: чёт ≥ 35 — Петя проиграл сразу. Ваня победил («без хода»).
25 → 26: Ваня из 26 может пойти ×2 → 52 (чёт, сам проиграет), но также +4 → 30 — а из 30 Петя, как мы видели, в ловушке: Ваня выиграет 2-м ходом.
25 → 29: аналогично, Ваня может создать «ловушку 30».

При любом ходе Пети Ваня выигрывает за ≤2 своих ходов. Но гарантированно первым ходом — не может (из 26 или 29 Ваня не достигает нечёт ≥ 35 за один ход). Значит S=25 — это ответ на В3.

11Что запомнить

Универсальный шаблон «f(state, n)»:
  1. Если игра кончилась — вернуть True/False по правилам победы.
  2. Если превысили лимит n — вернуть False.
  3. Посчитать все f(ход, n+1).
  4. Вернуть any на нашем ходу, all на ходу соперника.

Главная идея, которую надо понять один раз и запомнить: своим ходом мы выбираем лучшее, чужим ходом соперник выбирает лучшее для себя. Это any vs all. В коде одна буква разницы — всё остальное одинаково.

На следующем занятии: динамическое программирование по состоянию — когда задача разворачивается не по уровням хода, а по значению параметра.

Печать