В задачах о покрытии фигуры легко увлечься перестановкой деталей. Иногда полезнее сначала проверить, может ли нужное покрытие существовать вообще. Шахматная раскраска помогает заменить множество расположений одним подсчётом. Разберём самостоятельно составленный учебный пример для подготовки к математической олимпиаде; это не задание официального тура.
Доска с двумя удалёнными клетками
Возьмём прямоугольную доску из шести строк и восьми столбцов. Нумеруем строки сверху вниз, столбцы слева направо. Удалим клетки с координатами (1, 2) и (4, 7). Можно ли закрыть оставшиеся клетки прямоугольными домино размером 1 × 2? Каждая деталь должна занимать две соседние по стороне клетки, не выходить за границу и не перекрываться с другими.
Всего было 48 клеток, осталось 46. По площади потребовались бы 23 домино. Однако делимость площади на два ещё не означает, что детали удастся разместить: этот расчёт учитывает только количество клеток, а не их соседство.
Раскрасим клетки по правилу
Назовём клетку чёрной, если сумма номера строки и номера столбца чётная, и белой — если нечётная. У соседних по стороне клеток одна координата меняется на единицу, поэтому меняется и чётность суммы. Следовательно, каждое допустимое домино занимает одну чёрную и одну белую клетку независимо от того, лежит оно горизонтально или вертикально.
В каждой полной строке четыре клетки каждого цвета. На исходной доске их по 24. Для удалённых клеток получаем суммы 1 + 2 = 3 и 4 + 7 = 11: обе нечётные, значит, удалены две белые клетки. Осталось 24 чёрных и 22 белых.
Если бы покрытие существовало, 23 домино заняли бы ровно 23 чёрные и 23 белые клетки. Эти количества не совпадают с имеющимися. Получили противоречие, поэтому покрытие невозможно. Здесь не нужно обсуждать, какую деталь положить первой: довод относится сразу к любому расположению разрешённых деталей.
Почему важно вернуться к условию
Метод работает благодаря точной форме детали и соседству по стороне. Нельзя незаметно разрешить соединять диагональные клетки: такой ход уже не обязан захватывать разные цвета. Необходимо также покрывать каждую оставшуюся клетку ровно один раз. При перекрытиях простой подсчёт занятых цветов перестал бы описывать покрытие.
Равенство числа чёрных и белых клеток — необходимое условие, но само по себе оно не даёт способа уложить домино. Чтобы ответить «можно», потребуется построение или отдельное доказательство существования.
Изменим удалённую пару
Теперь на такой же доске удалим клетки (1, 1) и (1, 2). Покрытие можно предъявить: оставшиеся шесть клеток первой строки разбиваем на три горизонтальные пары, а каждую из пяти остальных строк — на четыре. Получаются 3 + 5 × 4 = 23 домино без пропусков и перекрытий. Здесь возможность установлена самим расположением, а не одним совпадением цветовых количеств.
При разборе своей попытки запишите, что именно делает раскраска: она показывает препятствие, общее для всех вариантов. Классическая идея проверки цветов разобрана также в лекции Дэниела Джексона в MIT, слайд 14. Размер доски, координаты и построение в этой статье выбраны самостоятельно.
