Условие
Прямоугольник покрыт в два слоя карточками
1×2 (над
каждой клеткой лежат ровно две карточки). Докажите, что карточки
можно разбить на два непересекающихся множества, каждое из
которых покрывает весь прямоугольник.
Решение
Докажем это утверждение для любой фигуры, а не только для
прямоугольника. Возьмем произвольную карточку
A0. Одна из ее
клеток покрыта клеткой другой карточки
A1, вторая клетка
A1 покрыта клеткой карточки
A2 и т. д. Цепочка карточек
A0,
A1,
A2,... замкнется, причем именно на карточке
A0, так как иначе какая-либо клетка будет покрыта трижды (не
исключено, что эта цепочка состоит только из двух карточек
A0
и
A1). Замкнутая цепочка карточек состоит из четного числа
карточек (для доказательства можно рассмотреть ломаную, каждое
звено которой соединяет центры клеток одной карточки; эта
ломаная имеет четное число и горизонтальных и вертикальных
звеньев). Поэтому для карточек, входящих в замкнутую цепочку,
искомым разбиением является разбиение на карточки с четными и
нечетными номерами. Все эти карточки выбрасываем и для
оставшихся карточек проделываем такую же операцию и т. д.
Источники и прецеденты использования
