ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35112
Темы:    [ Замощения костями домино и плитками ]
[ Процессы и операции ]
Сложность: 3+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Можно ли покрыть шахматную доску 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 найдется в любом случае.


Ответ

нельзя.

Источники и прецеденты использования

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .