|
|
 |
Условие
Квадрат разбит на n² ≥ 4 прямоугольников 2(n – 1) прямыми, из которых n – 1 параллельны одной стороне квадрата, а остальные n – 1 – другой. Докажите, что можно выбрать 2n прямоугольников разбиения таким образом, что для каждых двух выбранных прямоугольников один из них можно поместить в другой (возможно, предварительно повернув).
Решение
Назовём пару прямоугольников вложимой, если один из них можно вложить в другой.
Пусть горизонтальная сторона квадрата разбилась на отрезки с длинами a1, ..., an (слева направо), а вертикальная – на отрезки с длинами b1, ..., bn (сверху вниз). Переставив "столбцы" и "строки", можно считать, что a1 ≥ ... ≥ an и b1 ≥ ... ≥ bn. Обозначим через Qi,j прямоугольник разбиения со сторонами ai и bj. Заметим, что при i ≤ k и j ≤ l пара (Qi,j, Qk,l) вложима.
Поскольку a1 + ... + an = b1 + ... + bn, найдутся различные индексы i и j, для которых ai ≥ bi и aj ≤ bj. Можно считать, что i < j. Тогда существует такой индекс k ∈ [i, j], : что ak ≤ bk и ak–1 ≥ bk–1.
Мы утверждаем, что можно выбрать следующие прямоугольники: Q1,1, Q1,2, ..., Q1,k–1, Q2,k–1, ..., Qk,k–1, Qk–1,k, Qk,k, ..., Qk,n, Qk+1,n, ..., Qn,n (см. рис.). Их количество равно 2(k – 1) + 2(n – k + 1) = 2n. Любая пара из них, кроме (Qk,k–1, Qk–1,k), вложима по замечанию выше. Оставшаяся пара также вложима, поскольку ak ≤ bk и bk–1 ≤ ak–1 (для вложения один прямоугольник нужно повернуть на 90°).
