E7 Игры: парные стратегии, чётностные инварианты

Идея метода: в задачах об играх двух игроков (где каждый ходит по очереди) нужно определить, кто выигрывает при оптимальной игре обоих. Метод состоит в том, чтобы найти стратегию — правило ходов, которое гарантирует победу или ничью независимо от действий противника.

Три главных инструмента:

1. Стратегия первого игрока — первый ходит и сразу занимает «выгодную позицию» или создаёт угрозу, на которую у второго нет ответа.

2. Стратегия второго игрока (симметричная копия / «зеркало»): второй игрок на каждый ход первого отвечает «симметричным» ходом. Объекты разбиваются на пары, и второй «копирует» первого в паре. Пока первый может ходить — второй тоже может (и наоборот). Значит, первый иссякает первым или попадает в проигрышную ситуацию.

3. Чётностный инвариант: если после каждого хода меняется чётность какой-то величины (числа фишек, суммы, ячеек), то стороны оказываются «на разных чётностях» по отношению к финальному состоянию. Это определяет, кто туда попадёт.

Аналогия: «зеркальная стратегия» — как игра в поддавки с зеркалом: что бы ты ни делал, зеркало делает то же, и ты не можешь выиграть.

• Принцип стратегического кражи (strategy stealing): Если второй игрок имел бы выигрышную стратегию, то первый мог бы «украсть» её — сделать лишний ход и играть как второй. Если лишний ход не вреден (что бывает часто), то первый побеждает. Следствие: во многих играх второй игрок не выигрывает — побеждает первый или ничья. Условие: лишний ход должен быть не вреден. Когда использовать: доказательство «второй не выигрывает» без явной стратегии.

• Симметричная (зеркальная) стратегия: если позиции симметричны (центральная симметрия доски, пары фишек), второй игрок копирует каждый ход первого симметрично. Инвариант: симметрия позиции сохраняется после каждой пары ходов. Условие: игра симметрична и нет «аномалий» в центре. Когда использовать: задачи на досках, кольцах, симметричных фигурах — второй игрок побеждает или делает ничью.

• Чётностный инвариант: определяем величину $I$ (число ходов, сумма, число оставшихся объектов), которая меняется на нечётное число при каждом ходе. Тогда чётность $I$ строго чередуется. Если $I = 0$ — конец игры, и чётность $I_0 \pmod{2}$ определяет, чей это ход (значит, кто проигрывает$). *$Когда использовать:* задачи, где важно «кто сделает последний ход».

• Принцип позиций P и N: позиция «проигрышная» (P-позиция) — если игрок, который должен ходить, при оптимальной игре противника проигрывает. «Выигрышная» (N-позиция) — есть ход в P-позицию. Конечная позиция (ничего нельзя сделать) — P-позиция. Когда использовать: теоретический анализ игр типа Nim.

• Разбиение объектов на пары (парная стратегия): делим все позиции/объекты на пары так, чтобы второй игрок мог отвечать на ход в одном элементе пары ходом в другом. Пока у первого есть ход — у второго есть ответ, и первый «иссякнет» первым.

• Симметричная копия хода: если игра на симметричной доске, второй игрок ходит симметрично первому (например, через центр доски). Симметрия сохраняется, и второй всегда имеет ответ.

• Проверка чётности числа ходов: если полное число позиций (или ходов) чётно — побеждает второй (он делает последний ход); нечётно — первый. Но это работает только в «последовательных» играх без выбора.

• Выделение инварианта: найти количество/сумму/характеристику позиции, которая меняется строго определённым образом (на $k$ при каждом ходе). Проследить чётность до конечной позиции.

• Анализ малых случаев: выписать P/N-позиции для небольших значений параметра и найти закономерность (часто цикл с маленьким периодом).

• Жёсткое открытие (первый игрок захватывает центр): если у первого игрока есть «суперход» — например, занять центральную симметричную позицию — дальше он сам играет «зеркальную стратегию».

Поверхностные признаки (что буквально написано):
- «Двое играют по очереди», «первый/второй игрок», «ход состоит в том, чтобы...».
- «Кто сделает последний ход, выигрывает» или «проигрывает».
- «Докажите, что первый/второй игрок всегда выигрывает».

Структурные признаки (форма выражения, объекты):
- Игра с конечным числом состояний (фишки на доске, числа, кучки камней).
- Условие завершения игры строго определено (нельзя ходить — проигрыш, или последний ход — выигрыш).
- Позиция/доска обладает явной симметрией (центральной, осевой, кольцевой).

Цель задачи (что от тебя хотят):
- Определить, кто выигрывает при оптимальной игре обоих.
- Описать выигрышную стратегию (не только «кто», но «как именно ходить»).
- Найти выигрышные начальные позиции.

Задача 1. Разбиение на пары (ВсОШ-стиль)

Условие: На столе лежат 2024 монеты. Двое игроков ходят по очереди: каждый ход можно взять 1, 2 или 3 монеты. Кто берёт последнюю монету — выигрывает. Кто выигрывает при оптимальной игре?

Источник: тренировочная (классический Nim, уровень ВсОШ-9)

Как думать (рассуждение ученика$):
1. $Что вижу? Игра с монетами, берут 1-3. Классический вопрос «кто выигрывает». Триггер: задача на чётность и стратегию.$2. *$Анализ малых случаев:$* 1, 2, 3$ монеты — первый берёт всё и выигрывает. 4 монеты: что бы первый ни взял (1, 2 или 3), второй берёт остаток до 4 и выигрывает. Значит, 4 — P-позиция (проигрыш для ходящего). 5 монет: первый берёт 1, остаётся 4 — P-позиция для второго. Значит, 5 — N-позиция.$3. *$Закономерность:$* P-$позиции при числе монет, кратном 4: 0, 4, 8, 12, .... Выигрышная стратегия второго: после хода первого (взял $k$ монет) брать $4-k$ монет. Сумма хода двух игроков $= 4.
4. $Применяю к $2024:$ $2024 = 4 \times 506$ — кратно 4. Значит, это P-позиция: выигрывает второй.

Решение:

P-позиции (проигрышные для того, кто ходит): $0, 4, 8, \ldots, 4k$.
N-позиции: все остальные.

Стратегия второго: на ход первого (взял $k \in \{1,2,3\}$) отвечает взятием $4-k$ монет. Суммарно за два хода убирается ровно 4 монеты. Так как $2024 = 4 \times 506$, после $506$ раундов монеты иссякнут на ходу первого — и взять нечего.

Ответ: Выигрывает второй игрок.

Что главное: стратегия «в сумме за два хода = 4» — парная стратегия, основанная на чётностном инварианте.

Задача 2. Зеркальная стратегия на доске

Условие: Игра на доске $1 \times 2n$ (строка из $2n$ клеток). Первый игрок ставит крестик в любую свободную клетку, второй — нолик. Кто не может поставить фигуру — проигрывает. Кто выигрывает?

Источник: тренировочная

Как думать (рассуждение ученика$):
1. $Что вижу?* Симметричная доска (чётное число клеток). Игра заканчивается, когда все клетки заняты — всего $2n$ ходов. Ходы чередуются: первый делает нечётные ходы (1-й, 3-й,...), второй — чётные.$2. *$Ключевая идея: у доски $1 \times 2n$ есть ось симметрии — центр между клетками $n$ и $n+1$. Второй игрок использует симметричную стратегию: на каждый ход первого в клетку $i$ отвечает ходом в клетку $2n+1-i$.$3. *$Инвариант:* после каждой пары ходов позиция симметрична. Всего $2n$ ходов — второй делает последний (ход номер $2n$). Первый не может ходить после этого.

Решение:

Второй игрок применяет зеркальную стратегию: на ход первого в позицию $i$ отвечает ходом в позицию $2n+1-i$. Поскольку первый всегда ходит первым в пару свободных клеток, зеркальная клетка всегда свободна (симметрия сохраняется). Таким образом:
- Каждый раз, когда первый может ходить — второй тоже может.
- Всего $2n$ ходов — второй делает ход $2n$ (последний).
- Первый не может ходить на шаге $2n+1$ — и проигрывает.

Ответ: Выигрывает второй игрок.

Что главное: симметрия доски → зеркальная стратегия → второй всегда имеет ответ.

• Ошибка: путают «стратегию первого» и «стратегию второго». Начинают описывать стратегию, не уточнив, кто именно побеждает. Как избежать: сначала определите победителя (P/N-анализ или чётность), затем описывайте стратегию этого игрока.

• Ошибка: зеркальная стратегия работает не всегда. Если первый игрок занимает «центральный» объект (без пары), симметрия ломается. Как избежать: проверьте, что центральный элемент не критичен или что первый не может его занять раньше.

• Ошибка: игнорируют начальное состояние. «Второй выигрывает по зеркальной стратегии» — но если нечётное число объектов, зеркального ответа не хватит. Как избежать: проверяйте чётность/нечётность числа объектов перед выбором стратегии.

• Ошибка: «первый выигрывает, потому что ходит первым». Это не аргумент. Первый ход может быть невыгодным. Как избежать: всегда делайте P/N-анализ или явно указывайте выигрышный ход первого.

• Ошибка: описание стратегии без доказательства её работоспособности. «Второй копирует ход первого» — нужно доказать, что зеркальный ход всегда существует и допустим. Как избежать: явно покажите, что зеркальная позиция всегда свободна (используя инвариант симметрии).