Решение. Равеннские прямоугольники (#70)
Для удобства введём нотацию:
«большой» прямоугольник» = панно
«маленький» прямоугольник» = плитка
Решение раскрашиванием
I. Рассмотрим панно. Нанесём сетку, раскрашенную в шахматном порядке так, как показано на рисунке.
При этом, будем предполагать следующие условия:
1) размеры клеток сетки равны ½ x ½
2) один из узлов сетки совмещён с левым нижним углом панно (центр координат 0), а линии сетки направлены вдоль его сторон (оси x и y)
II. Рассмотрим произвольную плитку. У неё одна из сторон является целым числом (длина — целое число), размер клеток сетки равен ½ x ½, поэтому площадь пересечения плитки с чёрными клетками совпадает с площадью пересечения её с белыми клетками. Так как панно выложено плитками, аналогичное свойство выполняется и для него. Назовём это свойство основным.
III. Теперь из доказанного основного свойства панно следует, что одна из его сторон должна быть целым числом. Действительно, предположим, что это не так. Пусть размеры сторон панно равны x и y. Разобьём панно на четыре части, проведя линии, параллельные осям координат и пересекающие их в точках [x] и [y] (см. рисунок).
Рассмотрим верхний правый прямоугольник со сторонами {x} и {y}. Для него разность площадей пересечения с чёрными Sb и белыми Sw клетками будет равна
Sb — Sw = min ({x}, 1-{x}) min ({y}, 1-{y}) > 0,
так как по предположению 0 < {x}, {y} < 1. Остальные три части панно имеют каждая хотя бы одну целую сторону, следовательно, они обладают основным свойством. Таким образом, для панно, как состоящее из этих четырёх частей, не обладает основным свойством. Противоречие.
Решение по индукции
Докажем математической индукцией по количеству плиток.
База. Для одной плитки — очевидно.
Переход. Пусть верно для n, докажем для n+1.
Рассмотрим любую сторону панно и все плитки, примыкающие к этой стороне. Стороны прямоугольников, перпендикулярные данной стороне будем называть высотами, другие — ширинами. Если все высоты равны высоте панно, то исходное утверждение очевидно. Пусть не так, тогда найдём плитку P с наименьшей высотой.
а) Если у плитки P целая высота z, то разделим панно на две части по уровню этой высоты, как на рисунке пунктиром.
В результате получим два панно, в каждом из которых количество прямоугольников <= n, следовательно, можно применить предположение индукции.
б) Если высота нецелая, тогда у этой плитки целая ширина z. Так как плитка P — с наименьшей высотой, то к её верхней стороне примыкают плитки, сумма ширин которых равна z. Рассмотрим теперь среди них плитку с наименьшей высотой.
ба) Если высота целая, то поступаем аналогично а), то есть отрежем у всех рассматриваемых на данном шаге плиток основание по уровню данной высоты и объединим с плиткой P — получим новую плитку с целой шириной z (см. оранжевый пунктир на рисунке ниже). После объединения общее количество плиток панно уменьшилось хотя бы на одну. В то же время, так как высоты всех плиток, стоящих на плитке P, были укорочены на целое число, то их свойство иметь хотя бы одну целую сторону не нарушилось. Следовательно, можно применить предположение индукции.
бб) Если высота нецелая, то поступаем аналогично б)
Рано или поздно процесс закончится, именно найдётся плитка с наименьшей высотой, которая будет целым числом, так как на каждом шаге ширина плитки с минимальной высотой уменьшается на целое число.
