E18 Симметричная стратегия (копирование) в играх

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

Почему этот метод выделен отдельно от общих игровых стратегий (E7) и задач про доминошки (B7)? В E7 рассматриваются общие методы анализа игр (nim, ретроанализ, P/N-позиции). Здесь же центральная идея одна: симметрия поля + копирование. Это не частный случай ним-теории, а самостоятельный красивый приём. От B7 (доминошки) метод отличается тем, что там симметрия используется для покрытий, а здесь — для игровых стратегий.

Интуиция: представь танцора, который всегда зеркально повторяет движения партнёра. Как бы партнёр ни двигался, у танцора всегда есть ответное движение, и они никогда не столкнутся. Именно это и делает второй игрок: он «зеркалит» первого.

Для применения метода нужны три условия:
1. Игровое поле (или позиция) имеет ось или центр симметрии.
2. Начальная позиция симметрична (или её можно сделать симметричной первым ходом).
3. Симметричный ответ на любой допустимый ход тоже является допустимым ходом (симметрия сохраняет правила).

• Стратегия копирования (зеркальная стратегия). Пусть игровое поле имеет центр симметрии $O$ (или ось). Если второй игрок всегда отвечает на ход в $X$ ходом в $X' = $ (симметричное $X$ относительно $O$), то:
• Если $X$ — допустимый ход, то $X'$ тоже допустим (по симметрии правил).
• Второй всегда может сделать ход, пока первый может. Условие: симметрия правил относительно $O$. Когда использовать: доказательство победы второго игрока (или первого, если он первым занимает центр).
• Стратегия первого игрока через захват центра. Если поле имеет центр симметрии и первый игрок занимает центральный элемент, то он сам получает право на зеркальную стратегию. Условие: в начальной позиции центральный элемент свободен. Когда использовать: классическая задача с монетами на круглом столе.
• Инвариант симметрии. После каждого хода второго игрока позиция симметрична относительно $O$. Это означает, что второй игрок никогда не оказывается в ситуации «ход есть у первого, но нет у меня». Когда использовать: для строгого обоснования стратегии.

• Найти ось или центр симметрии поля — это первый шаг при анализе любой игры на симметричном поле.
• Разбить позиции на симметричные пары $\{X, X'\}$ и убедиться, что ход в $X$ всегда допустим, если допустим ход в $X'$.
• Проверить, что центральная позиция особая: если она одна и неспаренная, то первый захватывает её первым ходом и затем копирует.
• Формализовать стратегию: «Второй игрок после хода первого в $X$ делает ход в $X'$» — и проверить, что это всегда допустимо.
• Проверить граничные случаи: что происходит, если первый ходит в центр (при стратегии второго) или в уже занятую клетку?
• Убедиться, что выигрышное условие не нарушает симметрию: копирование гарантирует «не проиграть первым», но нужно понять, кто именно выигрывает в конкретных правилах.

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

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

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

Задача 1. Двое по очереди кладут монеты на круглый стол (монеты одинакового размера, нельзя накладывать). Тот, кто не может положить монету, проигрывает. Кто выигрывает при правильной игре?

Источник: классическая олимпиадная задача (Турнир городов, ВсОШ школьный тур; задача известна с середины XX века).

Как думать (рассуждение ученика$):
1. $Что я вижу? Игра на симметричном поле (круглый стол). Ходы — класть монету в свободное место. Первый или второй выигрывает?$2. *$Какой триггер? Симметричное поле + «кто не может — проигрывает» → думаю о зеркальной стратегии.$3. *$Первый ход мысли: есть ли у поля центр симметрии? Да — центр круглого стола. Если первый положит монету в центр, он займёт единственную точку, симметричную саму себе. После этого для каждой позиции, которую занял первый, есть симметричная позиция, куда может ответить второй... нет, логика обратная: первый хочет контролировать симметрию.$4. *$Ключевая идея:* первый кладёт монету точно в центр стола. Теперь стол симметричен относительно этого центра, а центр занят. Далее: на каждый ход второго (монета в позицию $A$) первый кладёт монету в центрально-симметричную позицию $A'$. Поскольку стол симметричен, если $A$ свободна, то $A'$ тоже свободна (иначе нарушилась бы симметрия, поддерживаемая стратегией). Поэтому первый всегда может ответить — и проигрывает тот, кто не может сделать ход, то есть второй.

Решение:
Стратегия первого игрока:
1. Первый ход: положить монету точно в центр круглого стола.
2. Каждый следующий ход: после того как второй положил монету в некоторую точку $A$, первый кладёт монету в точку $A'$, центрально симметричную $A$ относительно центра стола.

Докажем корректность: после каждого хода первого позиция центрально симметрична. Если второй может сделать ход (есть свободное место $A$), то место $A'$ тоже свободно (по симметрии позиции), и первый может сделать симметричный ход. Значит, первый никогда не оказывается без хода первым. Тот, кто проигрывает — это тот, кто не может ходить, то есть второй.

Ответ: первый игрок выигрывает. Его стратегия: занять центр стола первым ходом и зеркалить все ходы второго через центр.

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

Задача 2. На столе лежит ряд из $2n$ монет ($n \geq 1$). Двое по очереди берут по одной монете с любого из концов ряда. Тот, у кого в конце сумма монет больше, выигрывает. Первый игрок выигрывает или проигрывает?

Источник: тренировочная (дух ВсОШ регионального тура, 8–9 класс; классическая задача на зеркальную стратегию).

Как думать (рассуждение ученика$):
1. $Что я вижу?* Ряд из $2n$ монет, берут с концов. Нужно максимизировать сумму. Нечётное и чётное расположения монет — может быть симметрия?$2. *$Какой триггер? Симметричный ряд + двое берут с концов → думаю о зеркальной стратегии.$3. *$Ключевая идея: раскрась монеты в два цвета: нечётные позиции (1, 3, 5, ...) — красные, чётные (2, 4, 6, ...) — синие. Сумма красных монет = $R$, сумма синих = $B$. Первый игрок смотрит: $R \geq B$ или $B > R$? Допустим, $R \geq B$. Тогда первый берёт с левого конца (монета 1 — красная). Теперь на концах стоят монеты 2 (синяя) и $2n$ (синяя). Что бы второй ни взял — он берёт синюю монету. После хода второго на концах снова стоят нечётные монеты... нет, нужно пересчитать.$4. *$Правильная идея через зеркало: ряд из $2n$ монет — симметричный объект. Первый может выбрать: брать монеты с чётных мест или с нечётных. Конкретно: первый берёт крайнюю (скажем, левую). После этого ряд из $2n-1$ монет, и второй снова выбирает с конца. Первый всегда может «поддерживать чётность» своих позиций. Покажем точную стратегию.$5. *$Точная стратегия:* раскрасим монеты: позиции $1, 3, 5, \ldots, 2n-1$ — красные, $2, 4, \ldots, 2n$ — синие. Сумма красных $= R$, синих $= B$. Если $R \geq B$, первый всегда берёт монету с «красной» стороны: первый ход — монета 1 (крайняя левая, красная). Теперь на концах — монеты 2 (синяя) и $2n$ (синяя). Второй обязан взять одну из них — синюю. Снова на концах оказываются монеты одного чётного (красного) паритета. Таким образом, первый всегда берёт красные монеты и в итоге получает $R \geq B$.

Решение:
Пронумеруем монеты слева направо: $a_1, a_2, \ldots, a_{2n}$. Обозначим:$$R = a_1 + a_3 + a_5 + \ldots + a_{2n-1}, \quad B = a_2 + a_4 + \ldots + a_{2n}.$$ Как минимум одно из $R, B$ не меньше $(R+B)/2$. Допустим, $R \geq B$ (случай $B > R$ симметричен).

Стратегия первого: взять $a_1$ первым ходом. Теперь остаток ряда $a_2, \ldots, a_{2n}$ с концами $a_2$ и $a_{2n}$ — оба чётные позиции (синие). Какую бы монету ($a_2$ или $a_{2n}$) второй ни взял, на концах нового ряда оказываются монеты нечётных позиций (красные). Первый берёт крайнюю — и снова концы становятся синими. Таким образом:
- Первый всегда берёт монеты с нечётных позиций (все красные).
- Второй вынужден брать монеты с чётных позиций (все синие).

По окончании игры у первого сумма $R \geq B$ — сумма второго. Первый выигрывает (или в худшем случае делит при $R = B$).

Ответ: первый игрок выигрывает (или не проигрывает) при любом расположении монет.

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

• Ошибка: применять зеркальную стратегию, не проверив, что симметричный ход допустим → Почему неверно: если правила игры нарушают симметрию (например, ход в центр запрещён), стратегия ломается. → Как избежать: явно проверь для каждого типа хода, что его симметричный образ тоже допустим.
• Ошибка: путать, кто должен использовать зеркальную стратегию — первый или второй → Почему неверно: если центр существует и не занят, его занимает первый и затем копирует. Если центра нет (поле с чётным числом позиций), копирует второй. → Как избежать: проверь, является ли «центральная» позиция особой (не имеет пары) — её должен занять тот, кто хочет копировать.
• Ошибка: считать, что зеркальная стратегия автоматически означает победу → Почему неверно: стратегия гарантирует «не остаться без хода раньше соперника», но победное условие может быть другим (например, не «последний ход», а «максимальная сумма»). → Как избежать: после обоснования стратегии явно проверь выигрышное условие.
• Ошибка: забыть обосновать базовый случай (первый ход) → Почему неверно: стратегия копирования начинается со второго хода (или с особого первого хода), и нужно отдельно указать, что именно делается первым. → Как избежать: явно опиши первый ход и только потом — правило копирования.
• Ошибка: применять стратегию к несимметричному полю → Например, прямоугольная доска $m \times n$ с $m \neq n$ не имеет нужной симметрии для некоторых игр. → Как избежать: перед применением проверь, что поле и правила действительно симметричны.