Математика · объяснение и практика

Почему раскраска доски может запретить покрытие домино

Доказываем невозможность замощения через шахматную раскраску, считаем баланс цветов и отличаем необходимое условие от полноценной схемы покрытия.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Прямоугольное домино 1 на 2 закрывает две соседние по стороне клетки разных цветов шахматной раскраски. Поэтому в полностью покрываемой области количества клеток двух цветов должны совпадать. Нарушение баланса запрещает покрытие независимо от поворотов костяшек.

Свойство одной плитки связывает всю область

Окрасим квадратную сетку по чётности суммы номера строки и столбца. При переходе к соседней по стороне клетке сумма меняется на единицу, поэтому цвет противоположен. Каждая разрешённая плитка 1 на 2 использует одну клетку каждого цвета. Горизонтальный и вертикальный поворот сохраняют это свойство; диагональное положение не является покрытием двух клеток данной сетки.

Если плитки не перекрываются и не выходят за область, общее покрытие содержит столько же тёмных клеток, сколько светлых. Это вывод о любой раскладке, а не об одной неудачной попытке. Равная чётная площадь означает лишь правильное количество клеток на плитки; цветовой баланс добавляет более сильное необходимое ограничение.

Почему удаление углов меняет возможность

На доске 8 на 8 изначально по 32 клетки каждого цвета. Два противоположных угла имеют один цвет: их суммы координат отличаются на чётное число. После удаления этих двух клеток остаётся 30 одного цвета и 32 другого. Площадь 62 допускает по количеству 31 плитку, но они покрыли бы ровно по 31 клетке каждого цвета. Получается противоречие.

На прямоугольнике 6 на 8 аналогичный подсчёт начинается с 24 клеток каждого цвета. Удаление двух клеток одного цвета оставляет 22 и 24. Хотя оставшаяся площадь 46 чётна, покрытие домино невозможно. Важно проверить цвет удалённых клеток, а не только их положение на краю: название «угол» само по себе не заменяет подсчёт по конкретным размерам.

Пример

Из доски 6 на 6 удалили две клетки одного цвета. Сколько осталось клеток каждого цвета и возможно ли покрытие?

Изначально было по 18 клеток. После удаления остаются 16 и 18, поэтому покрытие плитками по одной клетке каждого цвета невозможно. Число оставшихся клеток 34 не устраняет цветовой запрет.

Баланс не строит раскладку автоматически

Две изолированные несоседние клетки разных цветов имеют равный баланс, но одна плитка не может их одновременно закрыть. Это простой пример, показывающий недостаточность одного подсчёта для произвольной области. Геометрическая связность, узкие переходы и расположение клеток могут создавать дополнительные препятствия. При равных количествах цветов нужно искать отдельную конструкцию или другой критерий.

Раскраска полезна именно тем, что для отрицательного ответа достаточно обнаружить нарушение. Если цвета сбалансированы, попытка пока не закончена. При другой форме плиток выбирают такую характеристику, которую каждая плитка меняет известным образом; привычная шахматная схема может перестать помогать. Свойство проверяют для всех разрешённых ориентаций, иначе доказательство будет относиться к более узкой задаче.

От чтения к действию

А теперь — вы

Из доски 10 на 10 удалили две клетки одного цвета. Почему замощение оставшейся области домино невозможно?

Частые вопросы

Чётной площади достаточно для замощения?

Нет. Она определяет только количество плиток. Дисбаланс шахматных цветов может запретить покрытие при чётной площади.

Равный баланс гарантирует покрытие любой области?

Нет. Например, две раздельные несоседние клетки разных цветов имеют баланс, но не покрываются одной прямоугольной плиткой.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться