|
|
 |
Условие
Имеется прямоугольная доска m×n, разделённая на клетки 1×1. Кроме того, имеется много косточек домино размером 1×2. Косточки уложены на доску, так что каждая косточка занимает две клетки. Доска заполнена не целиком, но так, что сдвинуть косточки невозможно (доска имеет бортики, так что косточки не могут выходить за пределы доски). Докажите, что число непокрытых клеток
а) меньше mn/4;
б) меньше mn/5.
Решение
a) Заметим, что столбец не может состоять из пустых клеток: ближайшую к такому столбцу доминошку можно сдвинуть. Докажем, что даже две пустые клетки рядом стоять не могут. Пусть такие нашлись, например, одна над другой. Будем "идти" по пустым клеткам вверх и вниз, пока не упрёмся с одной из сторон (пусть вверху) в доминошку. Если её нельзя сдвинуть вниз, то она горизонтальна, и под ее второй клеткой есть другая доминошка. Эту последнюю можно сдвинуть в сторону нашей группы пустых клеток.
Теперь ясно, что пустая клетка не может оказаться на границе прямоугольника: одна из трёх (двух для угловой клетки) соседних доминошек может быть сдвинута.
Ни в одном из квадратов 2×2 этого прямоугольника не может оказаться более одной пустой клетки. Действительно, согласно доказанному выше в таком квадрате две пустые клетки могут стоять только по диагонали, а две оставшиеся клетки должны быть заняты. Но тогда доминошка, которой принадлежит занятая клетка, сдвигается.
Разобьём теперь весь прямоугольник на квадраты 2×2, оставив на краю одну или две горизонтальные полоски высоты 1 и, возможно, одну вертикальную полоску ширины 1. В этих полосках пустых клеток нет, а в квадратах их не больше четверти. Таким образом, пустых клеток меньше mn/4.
б) Из а) следует, что каждая пустая клетка "окружена" четырьмя доминошками. Но две пустые клетки (a и b), разделённые одной клеткой (см. рис.), одновременно окружить нельзя. Значит, таких положений нет.
Замечания
баллы: 2 + 4
