Задания 19–21 проверяют умение анализировать игровые позиции, строить дерево ходов и находить выигрышные стратегии через перебор или анализ остаточных функций. Правильный шаблон действий и понимание терминов позволяют гарантированно набрать по три первичных балла.
Введение в теорию игр и формат ЕГЭ
Теория игр в ЕГЭ по информатике представлена заданиями 19, 20 и 21. Это игры с одной или двумя кучами камней, где игроки ходят по очереди и могут изменять количество камней согласно правилам.
Первый ход делает игрок А (чаще Петя или Полина), второй – игрок В (Ваня или Вероника). Побеждает тот, кто совершит последний ход, превратив товар в целевое состояние (обычно доведя сумму в куче до порога или ниже заданного минимума).
Практический смысл: такие задачи моделируют ситуации выбора хода в условиях ограниченного набора операций и выстраивания последовательности действий, гарантирующей победу вне зависимости от ответных шагов соперника.
Основные определения и подходы
Выигрышная и проигрышная позиция
- Выигрышная позиция — состояние игры, из которого текущий игрок может сделать ход в выигрышное состояние для себя независимо от ответных действий соперника.
- Проигрышная позиция — состояние, из которого каждая возможная линия игры ведёт к выигрышу соперника.
Дерево игры
Построение дерева ходов помогает визуализировать все возможные переходы между состояниями. В корневом узле – начальное число камней, далее разветвления по каждому допустимому действию. Листами считаются позиции, в которых заканчивается игра.
Совет: не обязательно прорисовывать всё дерево на бумаге. Достаточно отмечать уровни и анализировать остатки ходов (чётность глубины итераций).
Перебор и рекурсия
Алгоритмический шаблон на Python или псевдокод:
python
def win(x, moves, max_moves):
if x >= target: # достигнут порог
return (moves % 2 == player) # возвращает True/False по выигрышу
if moves == max_moves:
return False
for new_x in [x + a, x * b, ...]:
if not win(new_x, moves + 1, max_moves):
return True
return False
target– пороговое значение, при котором игра завершается.player– 0 для первого игрока, 1 – для второго.max_moves– ограничение глубины перебора (исходя из условия «не более N ходов»).
Шаблон решения заданий 19–21
- Понять условия:
- Исходное число камней X.
- Допустимые действия: прибавить k, умножить на m, убрать n, уменьшить в d раз и т. д.
- Целевая позиция: ≥ M (или ≤ M).
- Определить параметры перебора:
- Максимальное число ходов (обычно 2–3 для заданий 19–21).
- Чей ход проверить (для задания 19 – ход второго игрока; для 20 – второго хода первого игрока; для 21 – стратегии обоих).
- Реализовать рекурсивную функцию
f(x, moves):
- Базовый случай: достижение цели или превышение глубины.
- Перебор всех возможных ходов.
- Перебрать значения X по условию задачи:
- Задание 19: найти минимальное или максимальное X, при котором второй игрок выигрывает своим первым ходом после неудачного хода первого.
- Задание 20: найти X, при котором первый игрок не может выиграть за один ход, но может выиграть своим вторым.
- Задание 21: найти минимальные/максимальные X по одновременному условию стратегий обоих игроков.
- Вывести искомое значение.
Пример решения задания 19
Условие: игра с одной кучей, начальное S камней, операции – +1 или ×2, цель – ≥ 59; Петя ходит первым, Ваня вторым. Известно, что Петя не может выиграть за один ход, а по любому его первому ходу Ваня побеждает своим первым ходом. Найти минимальное S.
python
def win(x, moves):
if x >= 59:
return moves % 2 == 1 # 1 – ход Вани
if moves > 2:
return False
for new_x in (x+1, x*2):
if not win(new_x, moves+1):
return True
return False
# Ищем минимальное S
for S in range(1, 59):
# Петя не выигрывает сразу
if not win(S, 0):
# Ваня выигрывает после любого хода Пети
if all(win(move, 1) for move in (S+1, S*2)):
print(S)
break
Ответ: 19.
Особенности 2025 года
- Новые операции: к классическим +1 и ×2 часто добавили «−1» или «деление на 2» при чётном X.
- Изменённые пороги: целевые значения могут меняться (например, вместо 59 – 102).
- Две кучи: в задании 21 появляется второй контур с двумя кучами, где операции применяются к обеим.
Практический вывод: внимательно читайте условие на предмет новых операций и числа куч. Шаблон решения остаётся тем же, расширяется только набор действий.
Таблица: сравнение заданий 19–21
| Задание | Цель перебора | Глубина ходов | Что ищем |
|---|---|---|---|
| 19 | Первый ход Пети + первый Вани | 2 | Мин/макс X, обеспечивающие выигрыш Вани первым ходом |
| 20 | Два хода Пети | 3 | X, где Петя выигрывает на втором ходу |
| 21 | Все возможные линии (Пети и Вани) | 4 | Мин/макс X по двум условиям стратегий |
Кейсы и типовые сценарии
Сценарий 1: Одна куча, две операции
- Условия: +2 или ×3, цель ≥ 100, Петя ходит первым.
- Типичная ошибка: считать неверно глубину рекурсии (забывают ограничить ходы), из-за чего код уходит в бесконечный перебор.
- Решение: установить
max_movesравным количеству ходов по условию (например, не более 4) и проверять достижение цели до глубины.
Сценарий 2: Две кучи, три операции
- Условия: первая куча +1 или ×2, вторая куча −1 или ÷2, цель – обе кучи ≥ 50.
- Риски: количество комбинаций растёт в квадрате, перебор становится неэффективным.
- Совет: использовать мемоизацию, сохранять результаты
f(a,b,moves)в словаре.
Мини-чек-лист при решении
- Уточнить набор операций (добавление, умножение, уменьшение).
- Определить порог и направление сравнения (≥ или ≤).
- Рассчитать максимальное число ходов.
- Выбрать игрока для проверки стратегии (Первый, Второй).
- Написать рекурсивную функцию с выходом по базовому случаю.
- Проверить все варианты ходов для нужных глубин.
- Перебрать X в заданном диапазоне и отфильтровать по условиям задания.
Частые ошибки
- Пропуск базового случая «игра окончена» до проверки глубины.
- Неправильное определение, чей ход проверяется (ход Петя=0, Ваня=1).
- Перебор слишком малой глубины, когда правила требуют учитывать например три хода.
- Игнорирование новых операций, добавленных в 2025 г.
FAQ
1. Нужно ли всегда строить дерево полностью?
Нет. Достаточно понимать принцип «чёрез один ход» и определять чётность глубины. Реальный графический рисунок дерева не обязателен.
2. Как выбрать max_moves?
Ориентируйтесь на формулировку задачи: «не более N ходов» или «первый/второй ход». Обычно N = 2 или 3.
3. Что делать при двух кучах?
Расширить рекурсивную функцию на два параметра: f(a, b, moves) и применить все действия к обоим кучам в каждом ветвлении.
4. Как ускорить перебор?
Применить мемоизацию и убрать повторные вычисления для одних и тех же (x, moves) или (a, b, moves).
5. Какие операции встречаются чаще всего в 2025 году?
Классические: +1, +3, ×2, умножение на k, уменьшение на 1, деление на 2 при чётном значении.
6. Можно ли решать вручную?
При малом пороге (≤ 50) да, но в сложных вариантах с двумя кучами и большим диапазоном лучше использовать шаблонный код.