B7 Парная стратегия (доминошки)

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

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

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

Метод применяется в двух основных контекстах: (1) доказательство выигрышной стратегии второго игрока в комбинаторной игре; (2) доказательство невозможности покрытия доски фигурами определённого вида (когда пар распасться не получается).

• Принцип парной стратегии: Если позиционное множество можно разбить на пары $(a_1, b_1), (a_2, b_2), \ldots$ так, что ход на $a_i$ всегда может быть «парным образом» ответен ходом на $b_i$, то второй игрок выигрывает (или не проигрывает), всегда повторяя «парный» ответ. Условие: разбиение должно покрывать все позиции, которые может занять первый игрок. Когда использовать: игры, где побеждает тот, кто делает последний ход (или проигрывает тот, кто не может ходить).

• Критерий невозможности покрытия: Если при удалении $k$ клеток с доски $m \times n$ число клеток чёрного и белого цвета (по стандартной раскраске) перестаёт быть равным, то домино (или любая фигура, покрывающая одну чёрную и одну белую клетку) не может замостить оставшееся. Условие: фигура покрывает ровно 1 клетку каждого цвета. Когда использовать: задачи на покрытие досок доминошками, тетромино и т.д.

• Стратегия центральной симметрии: Если игровая доска или множество позиций симметрично относительно центра, второй игрок отвечает ходом, симметричным ходу первого относительно этого центра. Условие: доска имеет центральную симметрию, а правила игры инвариантны при этой симметрии. Когда использовать: игры на клетчатой доске с центральной симметрией.

• Раскраска в два цвета. Раскрась позиции (клетки, числа) в два цвета так, чтобы каждая фигура/ход захватывала ровно одну клетку каждого цвета — тогда равенство числа клеток необходимо для покрытия.
• Явное построение разбиения на пары. Для стратегии: выпиши конкретные пары $(a_i, b_i)$ и объясни, почему ответ на $a_i$ всегда $b_i$ (и наоборот).
• Симметрия относительно центра/оси. Найди ось или центр симметрии задачи и объяви стратегию «зеркального ответа».
• Инвариант чётности. Если ход меняет чётность какого-то параметра, а начальное состояние чётно, то второй игрок поддерживает чётность и выигрывает.
• Разбиение на «доминошки». Для покрытий: попробуй разбить фигуру/доску на доминошки и убедись, что ни одна из них не задета удалёнными клетками.
• Стратегия копирования хода. Если позиция симметрична, второй игрок буквально «копирует» ход первого в симметричное место.

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

Структурные признаки (форма выражения, объекты):
- Множество позиций чётное по числу, и интуитивно разбивается на пары «ход–ответ».
- Есть центральная или осевая симметрия у игрового поля.
- Задача про невозможность: удалили несколько клеток, нужно доказать, что покрытие невозможно.

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

Задача 1. Игра на клетчатой доске $2 \times n$

Условие: Двое по очереди ставят доминошки (размером $1 \times 2$) на прямоугольную доску $2 \times 2n$. Кто не может сделать ход, проигрывает. Кто выигрывает при правильной игре?

Источник: классическая задача (тренировочная)

Как думать (рассуждение ученика):
1. Вижу: доска $2 \times 2n$, доминошки, игра «кто не может — проигрывает». Это задача на выигрышную стратегию. Триггер: симметричная доска + игра двух игроков.
2. Метод: парная стратегия. Доска симметрична относительно вертикальной центральной оси.
3. Первый ход: второй игрок «отзеркаливает» каждый ход первого.
4. Ключевая идея: если первый ставит доминошку в левую половину, второй ставит симметричную в правую. Первый не может «сломать» симметрию — доска $2 \times 2n$ всегда делится центральной вертикалью на две равные части.

Решение:
Второй игрок использует стратегию центральной симметрии. Пронумеруем столбцы $1, 2, \ldots, 2n$. Каждая доминошка, поставленная первым игроком в столбцы $\{k, k+1\}$ (или вертикально в столбец $k$), получает «пару» в столбцах $\{2n+1-k-1, 2n+1-k\}$ (симметричных). Поскольку доска симметрична, после каждого хода первого игрока второй может сделать симметричный ход. Значит, второй игрок никогда не останется без хода раньше первого.

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

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

Задача 2. Угловые клетки шахматной доски

Условие: Из шахматной доски $8 \times 8$ удалены два угловых квадрата, расположенных на одной диагонали (например, левый верхний и правый нижний). Можно ли замостить оставшиеся 62 клетки доминошками?

Источник: классическая задача (тренировочная)

Как думать (рассуждение ученика):
1. Вижу: $8 \times 8$ минус два угла, доминошки. $62$ клетки — чётное число, значит формально число клеток не мешает. Триггер: удалены клетки, покрытие доминошками.
2. Метод: раскраска в два цвета (инвариант). Каждая доминошка закрывает одну чёрную и одну белую клетку.
3. Первый ход: раскрасить доску стандартно. Два угла на одной диагонали — одного цвета!
4. Ключевая идея: стандартная раскраска $8 \times 8$ даёт 32 чёрных и 32 белых. Удаляем два угла одного цвета: осталось 30 одного цвета и 32 другого. Доминошка всегда берёт 1+1 — невозможно покрыть 62 клетки с дисбалансом 2.

Решение:
Раскрасим доску в шахматном порядке. Левый верхний и правый нижний углы оба белые (или оба чёрные). После удаления: 30 белых, 32 чёрных (или наоборот). Каждая доминошка покрывает ровно 1 белую и 1 чёрную клетку. Значит, при любом покрытии число покрытых белых = число покрытых чёрных. Но $30 \neq 32$ — покрытие невозможно.

Ответ: Нельзя.

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

• Ошибка: не проверить, что разбиение на пары покрывает ВСЕ позиции. Нашёл «стратегию симметрии», но она работает не для всех возможных ходов первого. → Явно опиши, как ответить на любой ход первого — не только «типичный».
• Ошибка: применить раскраску, когда фигура берёт не 1+1 клетки разных цветов. Для тетромино-Г одна раскраска не работает. → Проверь: сколько клеток каждого цвета берёт фигура; если не 1+1 — нужна другая раскраска.
• Ошибка: объявить выигрышную стратегию без доказательства, что ход «ответа» всегда существует. Симметричный ход может быть уже занят. → Доказывай: если позиция $a$ свободна, то симметричная ей $b$ тоже свободна (по построению стратегии).
• Ошибка: спутать «первый выигрывает» и «второй выигрывает». Если первый первым делает ход на центр симметрии — второй уже не может «зеркалить». → Проверь: есть ли у первого игрока «особый» первый ход, ломающий стратегию второго.
• Ошибка: думать, что чётность числа клеток достаточна для возможности покрытия. $62$ клетки — чётное, но покрытие невозможно. → Чётность числа клеток — необходимое, но не достаточное условие.