Теория игр в ЕГЭ по информатике: выигрышные стратегии (№19–21)

Коротко о главном

В заданиях 19–21 два игрока по очереди делают ходы в игре с камнями (или числами), пока не достигнут заданного порога $S$. Победитель определяется правилами конкретной задачи (обычно выигрывает тот, кто первым достиг или превысил $S$, либо тот, после чьего хода куча стала равна или больше $S$). Задача — найти количество камней или условие, при котором у одного из игроков есть гарантированная выигрышная стратегия, независимо от действий соперника.

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

Определения и формулы/правила

Термин	Значение
Позиция	Текущее состояние кучи (число камней) или двух куч в паре $(a, b)$
Ход	Добавление от 1 до $t$ камней в кучу (правила хода задаются в условии)
Проигрышная позиция (П)	Из неё любой ход соперника ведёт к выигрышной для него позиции
Выигрышная позиция (В)	Из неё существует хотя бы один ход, ведущий соперника в проигрышную позицию
Финальная позиция	Куча $\ge S$ — игра завершена, определяется победитель

Основное правило анализа: $$\text{Позиция } n \text{ — П} \iff \forall k \in [1,t]:\ (n+k) \text{ — В для соперника}$$ $$\text{Позиция } n \text{ — В} \iff \exists k \in [1,t]:\ (n+k) \text{ — П для соперника}$$

Если ход — добавление от 1 до $t$ камней, то часто позиции делятся по модулю $(t+1)$: проигрышными оказываются позиции, для которых $n \equiv r \pmod{t+1}$ при некотором фиксированном остатке $r$, зависящем от $S$. Но это работает только для простой игры с одной кучей и фиксированным диапазоном ходов — в задачах с двумя кучами или с разными правилами для игроков нужен полный перебор от $S$ назад.

Алгоритм построения таблицы позиций:

1. Найти финальные позиции (обычно $n \ge S$) — определить, кто выиграл при их достижении.
2. Идти от больших $n$ к меньшим (от $S-1$ до 0 или до начального значения).
3. Для каждой позиции проверить все возможные ходы и определить, П это или В.
4. Итоговая позиция при $n=0$ (или начальное число камней) показывает, выигрывает ли первый игрок при оптимальной игре обоих.

Как применять

Пример 1 (задание 19). Куча — 3 камня. За один ход можно добавить 1 или 2 камня. Выигрывает тот, после чьего хода куча становится $\ge S$. Найти наименьшее $S$, при котором первый игрок выигрывает первым ходом.

Первый игрок выигрывает первым ходом, если может сразу сделать кучу $\ge S$: $3+1=4$ или $3+2=5$. Значит, при $S \le 5$ первый выигрывает немедленно. Наименьшее такое $S$ — любое $S \le 4$ (даже $S=1$ подходит), но по смыслу задачи обычно ищут границу, при которой выигрыш есть только за счёт немедленного хода — ответ $S \in \{1,...,5\}$, конкретное число зависит от формулировки.

Пример 2 (задание 20). Куча — 10 камней, ход — добавить 1, 2 или 3 камня, $t=3$. Значит, шаг деления позиций — $t+1=4$. Проигрышные позиции для игрока, который должен ходить: $n \equiv (S \bmod 4) \pmod 4$ при подходящем сдвиге. Строим таблицу от $S$ назад: позиции, из которых все ходы (+1,+2,+3) ведут в позиции, кратные 4 относительно $S$, — проигрышные. Далее проверяем, попадает ли начальная позиция $n=10$ в число проигрышных для первого игрока — если да, выигрывает второй, иначе первый должен указать выигрышный ход (обычно тот, что переводит соперника в П-позицию).

Пример 3 (задание 21, две кучи). Позиция задаётся парой $(a,b)$, ход — добавить камни в одну из кучи по своим правилам (у каждого игрока может быть свой диапазон ходов). Строим таблицу П/В для всех пар $(a,b)$ с $a,b < S$, начиная с ближайших к $S$ и двигаясь назад. Ищем количество значений $S$, при которых начальная позиция — проигрышная для первого игрока (то есть выигрышная для второго) — это и есть ответ на вопрос "при каких $S$ у второго игрока есть выигрышная стратегия".

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

• Путают, кто делает финальный ход. Нужно чётко понимать: выигрывает тот, кто дошёл до $S$ или тот, после чьего хода куча превысила $S$, — от этого зависит вся разметка позиций.
• Забывают проверить ВСЕ ходы соперника при определении проигрышной позиции — достаточно одного "хорошего" хода соперника, чтобы позиция стала выигрышной, а не проигрышной.
• Ошибка в границах диапазона ходов. Если разрешено добавлять от 1 до $t$, а не от 0, легко просчитаться на единицу и получить неверный шаг $t+1$.
• Применяют формулу с модулем не глядя на условие. Формула через $(t+1)$ работает только для симметричной игры (одинаковые ходы у обоих игроков, одна куча). При двух кучах или разных правилах для игроков нужен полный перебор, а не готовая формула.
• Путают "выигрышная стратегия есть" и "выигрышный ход есть только один". В задании 20 часто просят назвать конкретный выигрышный первый ход — нужно не просто определить статус позиции, а указать сам ход.
• Не учитывают, что у второго игрока может быть несколько ответных ходов на один и тот же ход первого — при построении дерева игры нужно рассматривать все ветви.

Где встречается на экзамене

• Задание 19: найти наименьшее (или все) значение $S$, при котором первый игрок может выиграть за один ход или за фиксированное число ходов.
• Задание 20: определить значение $S$ и указать конкретную выигрышную стратегию (последовательность ходов) первого игрока при оптимальной игре обоих.
• Задание 21: найти количество значений $S$ (или диапазон), при которых у второго игрока существует выигрышная стратегия независимо от ходов первого — самое сложное задание блока, часто требует построения полной таблицы позиций.