Шахматная доска и домино

Решение

Вопрос и ответ

Можно ли замостить оставшиеся 62 клетки доски костяшками домино 1x2?

Ответ: НЕТ, невозможно.

Доказательство через раскраску

Шаг 1: Понимание структуры

• Шахматная доска 8×8 имеет 64 клетки
• Удалены две диагонально противоположные клетки (например, a1 и h8)
• Остаётся 62 клетки
• Костяшка домино занимает ровно 2 клетки
• 62 клетки / 2 = 31 костяшка (по теории может подойти)

Шаг 2: Раскраска в чёрное и белое

Рассмотрим шахматную раскраску доски (как обычно: чередующиеся чёрные и белые клетки):

На доске 8×8:

• Белых клеток: 32
• Чёрных клеток: 32
• Итого: 64

Шаг 3: Какие клетки удаляются

Ключевое наблюдение: Диагонально противоположные углы доски имеют ОДИНАКОВЫЙ ЦВЕТ.

• Клетка a1 (левый нижний угол) - чёрная
• Клетка h8 (правый верхний угол) - чёрная

(В стандартной раскраске оба угла одного цвета)

Шаг 4: После удаления двух клеток

Остаётся:

• Белых клеток: 32
• Чёрных клеток: 32 - 2 = 30
• Итого: 62 клетки

Асимметрия: Белых на 2 больше, чем чёрных!

Шаг 5: Почему домино не подходит

Любая костяшка домино 1×2 при размещении на шахматной доске всегда занимает ровно одну белую и одну чёрную клетку.

Доказательство: домино размером 1×2 соединяет две соседние клетки, а соседние клетки в шахматной раскраске всегда разных цветов.

Шаг 6: Вывод

Если расставить 31 костяшку домино:

• Они займут 31 белую и 31 чёрную клетку
• Останется 1 белая клетка (32 - 31 = 1)
• И 0 чёрных клеток (30 - 31 = -1 — невозможно!)

Вывод: Замостить невозможно из-за несоответствия цветов.

Математическое доказательство

Лемма: Для любого мощения доски костяшками домино выполняется:

Количество белых клеток = Количество чёрных клеток

Доказательство леммы:

• Каждое домино занимает 1 белую + 1 чёрную клетку
• n костяшек займут n белых и n чёрных клеток
• Поэтому условие необходимо

Применение к нашей задаче:

• После удаления двух чёрных клеток: белых ≠ чёрных
• 32 ≠ 30
• Следовательно, мощение невозможно

Почему диагонально противоположные?

Если бы удалили две клетки РАЗНОГО цвета (например, a1 и h1):

• Оставалось бы: 31 белая + 31 чёрная
• 31 костяшка домино могли бы замостить доску (возможно)

Если бы удалили две клетки ОДНОГО цвета:

• Оставалось бы: 32 белая + 30 чёрная (или наоборот)
• Мощение невозможно (как в нашем случае)

Генерализация

Теорема о шахматной раскраске:

Для любой доски, мощение домино 1×2 возможно тогда и только тогда, когда удаленные клетки занимают равное количество белых и чёрных клеток.

Для доски 8×8:

• Удаляем 2 клетки одного цвета → мощение невозможно
• Удаляем 2 клетки разных цветов → мощение возможно (если доска связна)
• Удаляем 0 клеток → 32 белых + 32 чёрных → всегда мощится

Практическое применение

Этот метод доказательства (раскраска доски) используется в:

• Комбинаторике и теории графов
• Тестировании алгоритмов (поиск контрпримеров)
• Доказательстве невозможности в головоломках

Альтернативное доказательство через инвариант

Инвариант: Определим потенциал доски как разность количества белых и чёрных клеток.

• Исходный потенциал: 64 - 64 = 0
• После удаления двух чёрных: 32 - 30 = +2
• Каждое домино изменяет потенциал на 0 (занимает 1 белую и 1 чёрную)
• Финальный потенциал останется +2
• Но завершённое мощение требует потенциал = 0
• Противоречие → мощение невозможно

Ключевые выводы

1. Простота доказательства: Достаточно одной раскраски
2. Универсальность: Работает для любых удаляемых клеток одного цвета
3. Интуиция: Цвета как инвариант - мощная техника
4. Применимость: Метод расширяется на другие доски и геометрии