Задания № 19, 20, 21 · ЕГЭ

Комбинаторные игры

Как находить выигрышные позиции и строить стратегию

2 мин чтенияСложность: Обновлено 29 сентября 2026

Комбинаторные игры — это игры двух участников, в которых игроки по очереди делают ходы, полностью видят состояние игры и стремятся выполнить противоположные цели: один выиграть, другой — не дать ему выиграть. Анализ такой игры сводится к классификации позиций и выбору правильного хода.

Комбинаторная играСлово «комбинаторная» связано с перебором и анализом сочетаний возможных ходов.

Игра двух участников с полной информацией, последовательными ходами и конечным числом возможных состояний, в которой результат определяется действиями игроков, а случайность отсутствует. Для каждой позиции в игре можно определить, является ли она выигрышной или проигрышной для игрока, которому предстоит ход.

Выигрышные и проигрышные позиции

Позиция называется выигрышной позицией, если из неё существует хотя бы один ход в проигрышную позицию соперника. Проигрышная позиция — это позиция, из которой любой допустимый ход переводит игру в выигрышную позицию соперника. Конечная позиция без допустимых ходов обычно проигрышна для игрока, который должен ходить.

\[W(s)=\exists\,s'\in Next(s): L(s'),\qquad L(s)=\forall\,s'\in Next(s): W(s')\]

Здесь \(s\) — текущее состояние, \(Next(s)\) — множество состояний после одного хода, \(W(s)\) означает выигрышность, а \(L(s)\) — проигрышность. Эти правила образуют рекуррентную основу анализа игры методом динамического программирования.

№

Пример: прибавление 1 или 2

На столе лежит 7 камней. За ход можно убрать 1 или 2 камня; проигрывает тот, кто не может ходить. Позиция с 0 камнями проигрышна. Поэтому позиции 1 и 2 выигрышны, 3 проигрышна, 4 и 5 выигрышны, 6 проигрышна, а 7 выигрышна: нужно убрать 1 камень и оставить сопернику 6. Так строится стратегия: после своего хода оставлять проигрышное число камней.

Не путайте позицию и ход

Выигрышной или проигрышной бывает позиция, а не отдельный ход. Ход называют выигрышным, если он переводит текущую позицию в проигрышную позицию соперника. Если игрок ошибся и выбрал другой ход, выигрышная стратегия может быть потеряна.

Проверка

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

Главное за минуту

Главное

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