E16 Раскраски как инвариант

Метод состоит в том, что мы раскрашиваем клетки (или другие объекты задачи) в несколько цветов по некоторому правилу, а затем подсчитываем количество клеток каждого цвета. Если покрывающая фигура (домино, тромино, плитка) всегда накрывает ровно по одной клетке каждого цвета, то любое правильное покрытие обязано содержать равное количество клеток каждого цвета. Нарушение этого баланса немедленно доказывает невозможность покрытия.

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

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

Как выбирать раскраску — сердце метода. Всё зависит от того, как устроена плитка:
- Плитка 1×2 (домино): шахматная раскраска в 2 цвета. Каждая доминошка накрывает ровно одну чёрную и одну белую клетку.
- Плитка 1×k: раскраска столбцов (или строк) числами $0, 1, \ldots, k-1$ по модулю $k$. Каждая плитка накрывает ровно по одной клетке каждого класса.
- L-тромино (три клетки в форме L): 3-цветная раскраска $3\times 3$-блоками или диагональная. Каждый тромино накрывает клетки трёх различных цветов.
- Квадрат 2×2 или L-тетромино: 4-цветная раскраска $2\times 2$-блоками.
- Диагональная раскраска: цвет клетки $(i,j)$ определяется суммой $(i+j) \bmod k$; удобна для плиток, вытянутых по диагонали.

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

• Инвариант раскраски. Если каждая плитка покрывает ровно $c_1$ клеток цвета 1, $c_2$ клеток цвета 2, ..., $c_r$ клеток цвета $r$, то при любом полном покрытии доски из $N_1$ клеток цвета 1, $N_2$ цвета 2, ..., $N_r$ цвета $r$ должны выполняться соотношения $N_1 : N_2 : \ldots : N_r = c_1 : c_2 : \ldots : c_r$. Условие: каждая плитка покрывает одно и то же количество клеток каждого цвета. Когда использовать: доказательство невозможности замощения.
• Шахматная раскраска. Раскрасим доску в два цвета так, что соседние клетки имеют разные цвета (классические чёрные и белые). Домино $1\times 2$ или $2\times 1$ всегда накрывает одну чёрную и одну белую клетку. Условие: плитка — прямоугольник $1\times 2$. Когда использовать: любые задачи на замощение доминошками.
• Полосатая раскраска ($\bmod k$). Раскрасим столбцы (строки) числами $0, 1, \ldots, k-1$ циклически. Плитка $1\times k$ накрывает ровно по одной клетке каждого класса. Условие: плитка — полоска $1\times k$. Когда использовать: задачи о покрытии прямоугольника полосками фиксированной длины.
• 3-цветная раскраска для L-тромино. Раскрасим доску $3\times 3$ (или периодически, шагом 3) в 3 цвета так, что L-тромино накрывает ровно одну клетку каждого цвета. Условие: плитка — L-тромино (три клетки$). *$Когда использовать:* задачи о разрезании фигуры на L-тромино.
• Связь с инвариантом по модулю. Если клетке $(i, j)$ присвоить число $(i + j) \bmod k$ (или $i \bmod k$), то «подсчёт цветов» — это в точности подсчёт суммы значений по модулю. Доска замощается только если суммарное значение делится на $k$. Когда использовать: для нахождения нужного модуля аналитически.

• Выбрать число цветов = количество клеток в плитке. Если плитка состоит из $k$ клеток, часто помогает раскраска в $k$ цветов так, чтобы каждый экземпляр покрывал ровно по одной клетке каждого цвета.
• Подсчитать клетки каждого цвета на доске и сравнить с требуемым соотношением. Если числа не совпадают — покрытие невозможно.
• Проверить шахматную раскраску первой — это самый быстрый способ убить задачу на домино. Если чёрных и белых клеток разное количество, доминошками не замостить.
• Для полосок $1\times k$ раскрасить столбцы числами $0, 1, \ldots, k-1$ и посчитать суммарное количество клеток каждого класса. Замощение возможно только если все числа равны.
• Для нестандартных плиток нарисовать несколько экземпляров и проверить, какую раскраску они «уважают»: перебрать несколько кандидатур.
• Совмещать раскраску с другим инвариантом (например, паритетом суммы координат), если одна раскраска не даёт результата.
• Доказывать возможность конструктивно: если раскраска не даёт противоречия, строй явное покрытие — раскраска лишь показывает невозможность, но не гарантирует возможность.

Поверхностные признаки (что буквально написано):
- «Можно ли замостить...», «докажите, что нельзя разрезать...», «покройте доску фигурами...».
- Упоминается прямоугольная доска, шахматная доска, клетчатая бумага, прямоугольник.
- Плитки/фигуры имеют фиксированную форму: домино, тромино, L-образная, полоска $1\times k$.

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

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

Задача 1. Из шахматной доски $8\times 8$ вырезали два противоположных угловых квадрата (оба белого цвета). Можно ли замостить оставшиеся 62 клетки домино $1\times 2$?

Источник: классическая олимпиадная задача (ВсОШ, школьный тур, 7–9 класс).

Как думать (рассуждение ученика$):
1. $Что я вижу? Доска минус два угла — нужно доказать невозможность или построить замощение. Плитка — домино, значит сразу думаю о шахматной раскраске.$2. *$Какой триггер? «Замостить домино» → шахматная раскраска.$3. *$Первый ход: раскрашиваю доску в шахматном порядке. Стандартная $8\times 8$ содержит 32 белых и 32 чёрных клетки. Два вырезанных угла — оба белые (углы $(1,1)$ и $(8,8)$ имеют одинаковый цвет при стандартной шахматной раскраске). После вырезания остаётся 30 белых и 32 чёрных клетки.$4. *$Ключевая идея:* каждое домино покрывает ровно одну белую и одну чёрную клетку. Значит в любом допустимом замощении число белых клеток равно числу чёрных. Но $30 \neq 32$ — противоречие.

Решение:
Раскрасим доску $8\times 8$ в шахматном порядке: клетка $(i,j)$ белая, если $i+j$ чётно, и чёрная иначе. На полной доске ровно 32 белых и 32 чёрных клетки. Угловые клетки $(1,1)$ и $(8,8)$ оба имеют чётную сумму координат ($1+1=2$, $8+8=16$), то есть оба белые. После их удаления остаётся:$$\text{белых: } 32 - 2 = 30, \quad \text{чёрных: } 32.$$ Любое домино $1\times 2$ покрывает ровно одну белую и одну чёрную клетку (так как две соседние клетки всегда разного цвета). Значит при любом замощении $n$ доминошками закрывается ровно $n$ белых и $n$ чёрных клеток, то есть белых и чёрных клеток должно быть поровну. Но $30 \neq 32$, поэтому замощение невозможно.

Ответ: нет, нельзя.

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

Задача 2. Можно ли разрезать прямоугольник $6\times 5$ на L-тромино (фигуры из трёх клеток в форме буквы L)?

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

Как думать (рассуждение ученика$):
1. *$Что я вижу?* Прямоугольник $6\times 5 = 30$ клеток, плитка — L-тромино из 3 клеток. $30 / 3 = 10$ — делится нацело, значит аргумент «не делится» не работает. Попробую раскраску.$2. *$Каку раскраску выбрать?$* L-$тромино покрывает 3 клетки — значит пробую 3-цветную раскраску. Раскрашу столбцы числами $0, 1, 2, 0, 1, 2$ (то есть $j \bmod 3@@LATEXBLOCK_0_1@@\text{Цвет } r: \quad \#\{(i,j): 1\le i\le 6, 1\le j\le 5, (i+j)\equiv r \pmod 3\}.$$
Всего клеток 30, и при периодической раскраске с периодом 3 по обоим направлениям цвета распределяются приблизительно поровну. Точный подсчёт: $6 = 2\times 3$, $5 = 1\times 3 + 2$.
- Для каждой строки $i$ из 5 клеток: ровно $\lfloor 5/3\rfloor = 1$ полный цикл + 2 остатка. Строка $i$ содержит цвета $(i+1) \bmod 3, (i+2) \bmod 3, (i+3) \bmod 3, (i+4) \bmod 3, (i+5) \bmod 3$, то есть два раза один цвет и по одному разу два другие (из-за $5 = 3+2$).
- Суммируя по всем 6 строкам (по 2 строки каждого типа по модулю 3): каждый из трёх цветов встречается ровно $6\times 5/3 = 10$ раз.

Если замощение существует из 10 L-тромино, то каждый из 10 тромино покрывает ровно по одной клетке каждого цвета, итого — 10 клеток каждого цвета. Это совпадает! Раскраска противоречия не даёт.

Применим другой аргумент: рассмотрим площадь. $6\times 5 = 30 = 3\times 10$ — делится на 3. Ещё рассмотрим нечётность: одна сторона прямоугольника нечётная ($5$). Покажем, что прямоугольник $m \times n$ замощается L-тромино тогда и только тогда, когда $3 \mid mn$ и $\min(m,n) \ge 2$, но также требуется, чтобы хотя бы одна из сторон делилась на 2 или другое условие. На самом деле прямоугольник $6\times 5$ замощается L-тромино: явное разрезание существует (разбиваем $6\times 5$ на шесть блоков $2\times 3$, каждый из которых разрезается на два L-тромино).

Проверка: $2\times 3 = 6 = 2\times 3$, и блок $2\times 3$ действительно разрезается на два L-тромино. Шесть таких блоков $2\times 3$ покрывают $6\times 6 = 36 \neq 30$. Попробуем: два блока $3\times 4 = 12$ клеток и один блок $3\times 2 = 6$ клеток... Рассмотрим напрямую: разрежем $6\times 5$ на блоки $3\times 2$ (получаем 5 блоков по 6 клеток = 30). Каждый $3\times 2$ разрезается на два L-тромино. Итого 10 L-тромино. Замощение существует! Ответ — можно.

Ответ: да, можно. (Разбиваем $6\times 5$ на пять прямоугольников $3\times 2$; каждый $3\times 2$ разрезается на два L-тромино.)

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

• Ошибка: применить шахматную раскраску ко всем задачам без разбора → Почему неверно: шахматная раскраска работает только для домино $1\times 2$; для L-тромино или полоски $1\times 3$ она не различает нужных случаев. → Как избежать: сначала смотри на плитку — если она из $k$ клеток, ищи $k$-цветную раскраску.
• Ошибка: забыть проверить все ориентации плитки → Почему неверно: раскраска может работать для горизонтального домино, но не для вертикального. → Как избежать: нарисуй все ориентации плитки и проверь инвариант для каждой.
• Ошибка: считать, что «раскраска не даёт противоречия» = «замощение существует» → Почему неверно: раскраска — лишь необходимое условие. Равенство количества клеток каждого цвета не гарантирует возможность замощения. → Как избежать: если противоречия нет — ищи явную конструкцию или другой инвариант.
• Ошибка: неверно посчитать количество клеток каждого цвета → Почему неверно: арифметическая ошибка при подсчёте ведёт к неверному выводу. → Как избежать: для прямоугольника $m\times n$ при раскраске $\bmod k$ точно подсчитай, сколько столбцов (строк) каждого класса.
• Ошибка: пытаться объяснить невозможность покрытия без конкретного инварианта → Почему неверно: фразы «кажется, не влезает» или «пробовали все варианты» — не доказательство. → Как избежать: доказательство невозможности ВСЕГДА должно содержать явный инвариант — цвета, сумму, остаток.
• Ошибка: неправильно выбрать цвет клеток при нестандартной нумерации → Например, угловые клетки шахматной доски оба белые или оба чёрные зависит от соглашения. → Как избежать: явно зафиксируй правило: «клетка $(i,j)$ белая, если $i+j$ чётно» — и придерживайся его до конца.