Об одном разбиении прямоугольника

Квант 1973, №1 с. 14-16 Тег SUJ7

Об одном разбении прямогоolgника

А. Т. Коломов

В этой заметке решается задача М144. Найдите необходимые и достаточно условные условия, которые должны удовлетворять числа a, b, α, β, чтобы прямоугольник a×b можно было разрезать на несколько прямоугольников α×β.

Например, можно ли прямоугольник 50×60 разрезать на прямоугольники размерами:
a) 20×15; б) 5×8; с) 6,25×15;
e) (2−√2)×(2+√2).

Решение обобщает решение задачи 1 из статьи Сойфера «Клетчатые доски и полимно» («Квант» № 11, 1972).

Полное решение задачи М144 дает следующая теорема. Для того чтобы прямоугольник a×b можно было разрезать на прямоугольники α×β, необходимо и достаточно, чтобы одновременно выполнялись следующие условия:

каждое из чисел α и β должно быть в целое число меньше хотя бы однозою из чисел a, b.
Каждый из чисел a и b должен представление в виде mα + nβ, где m и n — неотрицательные числа α и β.

Доказательство. Обозначим большой прямоугольник через R, а маленький через p.

Достаточно есть. Если a=nα, b=mβ (m и n — натуральные числа), то, разбив одну из сторон прямоугольника R на m, а смежную с ней стороны на n равных частей, и затем проведя через точки деления прямые, параллельные сторонам R, мы тем самым разобем его на прямоугольники, равные р (рис. 1).

Если же a=n α=mβ, то в силу второго условия b допускает представление b=kα+lβ, где k и l можно считать положительными целыми числами. Тогда, разбив прямоугольник R на два прямоугольника P и Q размерами a×kα и a×lβ соответственно, мы сведем этот случай к уже рассмотренному (рис. 2).

Необходимость второго условия очевидна. Доказем необходимость первого условия. Возможны два случая:

Числа α и β consistemмы. Тогда без ограничения общности можно считать числа α, β, а и b целыми, так как этого всегда можно добиться

Рис. 1.

выбором подхождения единцы масштаба. Предположим теперь, что наше утверждение не верно, и для определения пустыни a, b не делятся на α. Разбив прямоугольник R на единчные квадраты, осуществим следующим образом правильную раскраску получаемой сетки в α различных цветов (раскраска называется правильной, если любые рядом стоящие α квадратов по вершине

тикали или горизонтали представляют все α цветов). Именно, окрасим в один и тот же цвет клетки, расположенные на диагонали, и душих сверху вниз и слева направо, причем цвета будем выбирать так, чтобы любые две такие диагонали, между которых расположены α—1 других, были окрашены одинаково. Легко видеть, что если нам удостсим осуществить требуемое разбиение прямогоугольника R, то каждый из данных α цветов будет представлен одним и тем же числом единичных квадратов в любом из полученных прямогоугольников, а стало быть, число квадратов во всем прямогоугольнике R, окрашенных в данной цвет, не зависит от выбора этого цвета. (На рисунке 3 представлена правильная 4-цветная раскраска).

Рис. 3.

Пусть $r_a$ и $r_b$ — остатки, полученные при делении a и b на α. Разобъем прямогоугольника R на три прямогоугольника A, B и C размерми $r_a \times r_b$ , $(a - r_a) \times r_b$ и $a \times (b - r_b)$ соответственно так, чтобы A занимал верхний левый угол исходного прямогоугольника R, B примыкал сизу к A, а C был расположен справа от A и B (рис. 4).

Рис. 4.

Рис. 5.

В прямогоугольнике B каждый цвет представлен одинаковым числом квадратов, так как α—r_a делится на α. Это же утверждение справедливо и для прямогоугольника C. Поэтому в силу предыдущего замечания оно должно выполнять и в A.

Рассмотрим прямогоугольник A более внимательно. Нас интересют три диагонали, расположенные в нем, одна из которых идет излевого верхнего угла A и окрашена в $i_1$ -й цвет, а две другие прямыхют к ней с обеих сторон и окрашены в $i_2$ -й и $i_\alpha$ -й цвет. Очевидно, что каждый из названных цветов может встретиться в прямогоугольнике A только на указанных диагонали. Но тогда, если $r_a \leqslant r_b$ , то число клеток $i_\alpha$ -го цвета на единицу меньше, чем число клеток $i_1$ -го цвета (рис. 5), если же $r_a > r_b$ , то число клеток $i_2$ -го цвета на единицу меньше, чем число клеток $i_1$ -го цвета (рис. 6). В обихх случае мы приходим к противоречию.

Пусть α и β несоизмеримы, и для определения α<β.

Если любые два прямогоугольника разбиения ориентированы одинаково по отношению к сторонам R (инными словами, больше стороны этих прямогоугольников параллельны одной и той же стороне исходного прямогоугольника), то утверждение теоремия очевидно.

Покажем, что случай с различной ориентицией прямогоугольников р невозможен. Предположив противное,

можно считать без ограничения общности, что уже к основанию прямогольника $R$ применяют прямогольники $\rho$ различной ориентации. Разобъем слой прямогольников $\rho$ , прямых коэффициентов $R$ , на фрагменты из одинаково ориентированных прямогольников так, чтобы прямогольники двух соседних фрагментов имели различную ориентацию.

Рис. 6.

Так как любые два рядом стоящих фрагмента имеют разную высоту, то прямогольники любого «низкого» фрагмента лежат на дне «колодца» (рис. 7), стенки которого образованы боковыми сторонами соседних фрагментов (одной из стенок, впрочем, может служить и боковая сторона прямогольника $R$ ).

Ввиду несомзмеримости $\alpha$ и $\beta$ каждой такой колодец должен быть заполнен прямогольниками той же ориентации, что и прямогольники фрагмента, находящемся на его дне. Как только это заполнение произойдет, так точас же каждой из «высоких» фрагментов оказывается сам на дне «колодца», стенки которой будут образованы боковыми сторонами соседних комплексов, состоящих из прямогольников иной ориентации, заполненных предыдушие «ко-

Рис. 7.

лодцы». После заполнения новых образованных колодцев у нас немедленно возникнет новое (рис. 8) и так далее.

Поэтому на каждом шаге области заполнения прямогольники будут ограничена сверху ломаной, имеющей хотя бы одно углубление, а, стало быть, в этом случае заполнение всего $R$ прямогольники $\rho$ невозможно.

Тем самым теорема полностью доказана.

Теперь посмотрим, на какие из прямогольников, перечисленных в условиям, можно разбит прямогольник $50 \times 60$ .

Рис. 8.

a) На прямогольники $20 \times 15$ разбит можно (по теореме).

b) На прямогольники $5 \times 8$ разбит нельзя, поскольку на 8 не делится ни 50, ни 60.

b) Разбение на прямогольники $6,25 \times 15$ оченьindo (оба числа 50/6,25 и 60/15 — целые).

г) На прямогольники $(2 + \sqrt{2}) \times (2 - \sqrt{2})$ разбит нельзя (не выполнено условия (1) теоремы).

Попробуйте сами привести primer такой случа, когда в теореме условия (1) выполнено, а условия (2) — нет.