Условие
Можно ли покрыть шахматную доску 8×8 доминошками 2×1
так, чтобы никакие две доминошки не образовывали квадратик 2×2?
Подсказка
Предположите, что это возможно, и исходя из этого предположения
постройте из доминошек "лесенку", которая начинается с угла доски.
Решение
Докажем, что всегда образуется хотя бы один квадратик 2×2.
Предположим противное – доска покрыта доминошками так, что ни одного
квадратика не образуется.
Занумеруем горизонтальные ряды доски числами от 1 до 8, а
вертикальные ряды – буквами a, b, c, ..., h (как при записи ходов в шахматной
партии).
Рассмотрим доминошку, покрывающую угловое поле a1.
Пусть, для определенности, эта доминошка горизонтальная, т.е.
покрывает еще поле b1.
Рассмотрим доминошку, покрывающую поле a2.
Если бы она была горизонтальной, то она образовывала бы квадратик
2×2 с первой доминошкой.
Следовательно, эта доминошка вертикальная, и она покрывает поля
a2, a3.
Далее, рассмотрим доминошку, покрывающую поле b2.
Если бы она была вертикальной, то она образовывала бы квадратик
2×2 с предыдущей доминошкой.
Рассматривая далее доминошки, покрывающие поля
b3, c3, c4, d4, d5, ..., мы построим "лесенку" чередующихся
горизонтальных и вертикальных доминошек,
занимающих пары полей (b2,c2),(b3,b4),(c3,d3),(c4,c5),(d4,e4), ..., (g7,h7).
После этого остается замкнутое пространство из двух клеток g8, h8,
которое должно заниматься одной доминошкой, образующей квадратик
2×2 с доминошкой (g7,h7).
Тем самым доказано, что квадратик 2×2 найдется в любом случае.
Ответ
нельзя.
Источники и прецеденты использования
