Игра (задача)

Для улучшения этой статьи желательно?: Викифицировать статью. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.

У этого термина существуют и другие значения, см. Игра (значения).

Игра — тип олимпиадных задач по математике, в которых требуется проанализировать стратегию игры и/или назвать победителя этой игры. Обычно заканчивается традиционным вопросом: «кто выиграет при правильной игре?»

Характеристики игр

Как правило, в задачах этого типа игры:

• детерминированы
• финитны
• с полной информацией
• включают ровно двух участников
• с невозможной (по правилам) ничьей

Отклонения от указанных характеристик единичны. Часть задач состоит как раз в доказательстве этих характеристик.

Отношение к теории игр

Указанные задачи, как правило, не предполагают знания теории игр. Тем не менее, отдельные положения теории игр — интуитивно очевидные — могут использоваться (см. ниже).

Используемые идеи

В задачи-играх используются самые разные методы решения, однако есть несколько часто повторяющихся идей:

1. инвариант — один из игроков каждым своим ходом приводит состояние игры в некоторое состояние (например, сумма оставшихся незанятыми полей) и такое состояние является выигрышным. А игра является финитной
2. выигрышность доказывается «с конца», с использованием идей динамического программирования: сначала доказывается, что находясь в одном из «предпоследних положений» можно попасть в «последнее» (выигрышное), затем — что из некоторого множества «предпредпоследних» можно попасть только в «предпоследнее» и так далее, пока не докажем, что «предпред…предпоследнее» положение является начальным. (См. функция Гранди).
3. необязательно разрабатывать стратегию, чтобы доказать её существование (при этом достаточно доказать т. н. «чистое существование» стратегии, не конструируя её явно).
4. если в финитной детерминированной игре с двумя участниками доказать невозможность выигрышной стратегии одного из участников, значит второй выиграет.
5. т. н. передача хода: если в некоторой ситуации игрок А может передать ход противнику, то у А позиция не хуже, чем у его противника.

«Правильная игра»

«Правильной игрой» в задачах этого класса называется выигрышная стратегия из теории игр — стратегия, придерживаясь которой игрок выиграет при любых ответных действиях противника.