Урок 2. Раскраски и замощения: шахматная доска как оружие

Олимпиадная математика

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

🎯 Что ты узнаешь

Шахматную раскраску и почему домино её «уважает»
Как доказывать невозможность замощения через подсчёт цветов
Раскраски не в 2, а в 3 и более цветов — для тримино и других фигур
Как выбирать раскраску под конкретную фигуру

📖 Разбираемся в теме

Шахматная раскраска

Раскрасим доску $8 \times 8$ в чёрный и белый как шахматную: соседние по стороне клетки разного цвета. Тогда чёрных клеток 32 и белых 32.

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

📌 Запомни: Если фигуры замощения всегда покрывают равное число клеток каждого цвета, а на доске цветов поровну не хватает — замощение невозможно.

Классика: доска без двух углов

Вырежем из доски $8 \times 8$ две противоположные угловые клетки. Останется 62 клетки. Можно ли замостить их 31 костяшкой домино?

Противоположные углы шахматной доски — одного цвета (проверь: клетки $(1, 1)$ и $(8, 8)$ обе, скажем, чёрные). Убрав две чёрные, получим 30 чёрных и 32 белых. Но каждое домино берёт по одной клетке каждого цвета, значит 31 домино взяли бы 31 чёрную и 31 белую. А чёрных всего 30 — противоречие. Замостить нельзя. ∎

🤔 А знаешь ли ты? Эта задача называется «задача о мутированной шахматной доске» и её любят задавать на собеседованиях. Без идеи раскраски она кажется «переборной» и безнадёжной, а с раскраской решается в две строки.

Раскраски в несколько цветов

Для фигур посложнее двух цветов мало. Возьмём прямое тримино (полоска $1 \times 3$ ). Раскрасим доску в три цвета по диагоналям — клетку $(i, j)$ красим в цвет $(i + j) mod 3$ . Тогда любая полоска $1 \times 3$ (горизонтальная или вертикальная) накрывает по одной клетке каждого из трёх цветов. Это мощный детектор для задач с тримино.

💡 Правило подбора: раскрашивай так, чтобы твоя фигура при любом положении покрывала цвета поровну или хотя бы предсказуемо. Тогда несовпадение количеств цветов на доске = невозможность.

L-тримино и раскраска в 4 цвета / другие трюки

Не всякая фигура ведёт себя одинаково при повороте — тогда одноцветный подсчёт не срабатывает, и приходится комбинировать: раскраска + чётность, или раскрашивать не всю доску, а только «опасные» клетки.

⚠️ Раскраска доказывает только невозможность. Если раскраска «не запрещает» — это ещё не значит, что замощение существует; его нужно предъявить явно.

✍️ Разбор задачи

Задача. Можно ли замостить доску $10 \times 10$ прямоугольниками $1 \times 4$ (полосками из четырёх клеток, которые можно класть и горизонтально, и вертикально)?

Решение. Обычная шахматная раскраска тут бессильна: полоска $1 \times 4$ всегда берёт 2 чёрные и 2 белые клетки, и никакого перекоса не возникает. Нужна более хитрая раскраска.

Раскрасим столбцы циклически в цвета $1, 2, 3, 4, 1, 2, 3, 4, 1, 2$ . Посчитаем, сколько клеток каждого цвета. Цвета столбцов: $1, 2, 3, 4, 1, 2, 3, 4, 1, 2$ — цвет 1 в столбцах ${1, 5, 9}$ (3 столбца), цвет 2 в ${2, 6, 10}$ (3 столбца), цвет 3 в ${3, 7}$ (2 столбца), цвет 4 в ${4, 8}$ (2 столбца). Каждый столбец содержит 10 клеток, поэтому:

цвет 1: $30$ клеток, цвет 2: $30$ , цвет 3: $20$ , цвет 4: $20$ .

Горизонтальная полоска $1 \times 4$ покрывает 4 столбца подряд — по одной клетке каждого из 4 цветов. Вертикальная полоска стоит в одном столбце — покрывает 4 клетки одного цвета.

Пусть в замощении $h$ горизонтальных и $v_{1}, v_{2}, v_{3}, v_{4}$ вертикальных полосок в столбцах цветов $1, 2, 3, 4$ . Клеток цвета 3 всего 20, их дают горизонтальные (по одной на каждую) и вертикальные цвета 3 (по 4): $h + 4 v_{3} = 20$ . Аналогично цвет 4: $h + 4 v_{4} = 20$ , цвет 1: $h + 4 v_{1} = 30$ , цвет 2: $h + 4 v_{2} = 30$ .

Вычтем первое из третьего: $4 v_{1} - 4 v_{3} = 10$ , то есть $v_{1} - v_{3} = 2, 5$ — не целое! Противоречие. Значит, замостить доску $10 \times 10$ полосками $1 \times 4$ невозможно. ∎

Красиво, правда? Одна хитрая раскраска столбцов — и всё разваливается на арифметику.

📝 Задачи

Из доски $8 \times 8$ вырезали одну белую и одну чёрную клетку (произвольные). Всегда ли оставшиеся 62 клетки можно замостить 31 домино? Обоснуй (тут ответ «да» — попробуй придумать идею, почему).
Можно ли замостить доску $5 \times 5$ костяшками домино $1 \times 2$ ? Почему?
Доску $6 \times 6$ замостили 18 костяшками домино. Докажи, что найдётся прямая (горизонтальная или вертикальная линия сетки), которая не пересекает ни одной костяшки. (Знаменитый факт; но сначала попробуй хотя бы для $4 \times 4$ .)
Можно ли доску $8 \times 8$ замостить 21 прямым тримино $1 \times 3$ и одним квадратиком $1 \times 1$ ? Если да — где может стоять квадратик? (Используй раскраску в 3 цвета.)
Комнату $10 \times 10$ хотят выложить плитками $1 \times 4$ и $2 \times 2$ . Осталась одна плитка $2 \times 2$ , а вместо неё привезли $1 \times 4$ . Докажи, что теперь выложить пол этими плитками нельзя (то есть заменить одну $2 \times 2$ на одну $1 \times 4$ и переложить весь пол не удастся).
Можно ли замостить доску $6 \times 6$ уголками-тримино (L-тримино из 3 клеток)? А доску $5 \times 6$ ?
На доске $8 \times 8$ отметили центры всех клеток. Можно ли соединить их одной замкнутой ломаной из 64 звеньев так, чтобы каждое звено соединяло центры соседних по стороне клеток и ломаная проходила через каждый центр ровно раз? (Раскраска подскажет ответ.)
⭐ Доску $2^{n} \times 2^{n}$ с одной вырезанной (любой) клеткой всегда можно замостить L-тримино (уголками из 3 клеток). Докажи это для всех $n \geq 1$ . (Подсказка: индукция и деление доски на 4 четверти.)