Задача 109638

Темы:    [ Покрытия ] [ Шахматная раскраска ] [ Подсчет двумя способами ] [ Геометрия на клетчатой бумаге ]

Сложность: 5- Классы: 8,9,10

Условие

Автор: Евдокимов М.А.

Можно ли прямоугольник $5 \times 7$ покрыть уголками из трёх клеток (т.е. фигурками, которые получаются из квадрата $2 \times 2$ удалением одной клетки), не выходящими за его пределы, в несколько слоёв так, чтобы каждая клетка прямоугольника была покрыта одинаковым числом клеток, принадлежащих уголкам?

Решение 1

Покрасим клетки прямоугольника в черный и белый цвета так, как показано на рисунке. Рассмотрим $12$ чёрных клеток. Никакие две из них не могут быть покрыты одним уголком, поэтому, если прямоугольник покрыт уголками в $k$ слоёв, то уголков хотя бы $12k$. Тогда суммарная площадь всех уголков не менее $36k$, однако, площадь $k$ слоёв равна $35k$ – противоречие.

Решение 2

Покрасим клетки прямоугольника в чёрный и белый цвета так, как показано на рисунке. В черные клетки запишем число $-2$, а в белые – число $1$. Заметим, что сумма чисел в клетках, покрываемых любым уголком, неотрицательна, следовательно, если нам удалось покрыть прямоугольник в $k$ слоёв, удовлетворяющих условию, то сумма $S$ чисел по всем клеткам, покрытым уголками, неотрицательна. Но если сумма всех чисел в прямоугольнике равна $s$, то $S=ks=k(-2 \cdot 12+23 \cdot 1)=-k > 0$. Получим противоречие.
Аналогично доказывается, что покрытия, удовлетворяющего условию задачи не существует, если прямоугольник имеет размеры $3 \times (2n+1)$ и $5 \times 5$. Прямоугольник $2 \times 3$ можно покрыть в один слой двумя уголками, прямоугольник $5 \times 9$ – в один слой пятнадцатью уголками, квадрат $2 \times 2$ – в три слоя четырьмя уголками. Комбинируя эти три покрытия, нетрудно доказать, что все остальные прямоугольники $m \times n$ ($m,n \ge 2$) можно покрыть уголками, удовлетворяя условию.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1996
Этап
Вариант	5
Класс
Класс	9
задача
Номер	96.5.9.8