Текст статьиВасильев Н. Б., Гальперин Г. А. Упаковка квадратов // Квант. — 1973. — № 4. — С. 35—37.
Эта заметка посвящена решению одной задачи из «Задачника « Кванта» (М155).
Дано несколько квадратов, сумма площадей которых равна $1$. Доказать, что их можно поместить без наложений в квадрат площади $2$.
Мы приведём два решения этой задачи, основанные на двух разных способах укладки квадратов, и обсудим некоторые её обобщения. Итак, пусть нам дано несколько квадратов общей площадью 1. Занумеруем их в порядке убывания сторон, т. е. так, чтобы сторона $k$-го по номеру квадрата была не меньше, чем сторона ($k+1$)-го($k=1$, 2, 3, $\ldots$). Мы должны доказать, что все эти квадраты можно разместить в квадрате со стороной $\sqrt2$.
Первое решение. Проведём на плоскости горизонтальный отрезок длины $\sqrt2$, а из его концов — вертикальные лучи. В образовавшуюся «полуполосу» (рис. 1) мы будем упаковывать квадраты.
Способ упаковки очень прост. Положим первый, самый большой квадрат в левый нижний угол (сторону этого квадрата мы обозначим через $x$), рядом с ним справа — второй по величине квадрат и т. д. до тех пор, пока очередной квадрат не перестанет умещаться в пределах полуполосы. Закончив «первый этаж», строим «перекрытие» — продолжаем верхнюю сторону левого квадрата на всю ширину полосы, на полученном отрезке точно так же строим «второй этаж», затем — третий и т. д., пока не кончатся все квадраты (рис. 2).
Теперь для того, чтобы доказать утверждение задачи, мы должны доказать, что высота $h$ (см. рис. 2) не превосходит числа $\sqrt2$. (Прежде чем читать решение дальше, попробуйте провести это доказательство сами!)
Рис. 1Рис. 2Рис. 3
Для этого, считая величины $h$ и $x$ заданными, оценим снизу сумму площадей квадратиков, упакованных в полуполосу. Перенесём мысленно каждый из квадратиков, прилежащих к левой «стене» (кроме самого нижнего квадрата $x\times x$), в конец предыдущего этажа, как показано на рисунке 3. Из способа построения этажей следует, что все эти квадраты вылезут за правую стену. Теперь продлим горизонтальные стороны каждого из этих новых квадратов влево вплоть до самого левого квадрата соответствующего этажа (при этом образуются прямоугольники, которые на рисунке 3 обведены красными линиями). Ясно, что сумма площадей всех квадратов (кроме $x\times x$) не меньше, чем сумма площадей полученных прямоугольников. Поскольку горизонтальное основание каждого из прямоугольников не меньше $\sqrt2-x$, а сумма их высот равна $h-x$, то сумма площадей всех прямоугольников не меньше $(\sqrt2-x)(h-x)$, следовательно, сумма площадей всех квадратов не меньше $x^2+(\sqrt2-x)(h-x)$.
Но по условию сумма их площадей равна 1. Итак,
$$
x^2+(\sqrt2-x)(h-x)\le1,
$$
откуда
$$
h\le\dfrac{1-x^2}{\sqrt2-x}+x=\sqrt2{\left[3-\left(y+\dfrac1y\right)\right]},
$$
где
$$
y=2-x\sqrt2.
$$
Следовательно, поскольку величина $y+\dfrac1y$, стоящая в круглых скобках, при любом $y$ не меньше 2, $h\le\sqrt2$.
Второе решение. Если в первом решении описать способ расстановки квадратов было очень легко, а основную трудность составляло доказательство нужной оценки, то во втором решении, наоборот, трудно описать способ упаковки (а оценка будет почти очевидной). Не вполне точные описания приводимой ниже упаковки предложили несколько читателей.
Мы опишем здесь способ упаковки совершенно формально. Описание «алгоритма» — предписания, согласно которому мы предлагаем упаковывать квадраты, — содержится в следующем абзаце. После того как описанная там операция проделана $k$ раз, в квадрате $\sqrt2\times\sqrt2$ оказываются размещёнными первые $k$ квадратов (мы по-прежнему считаем, что они занумерованы в порядке убывания сторон), а остальная часть квадрата $\sqrt2\times\sqrt2$ разбита на $k+1$ прямоугольников, которым приписаны определённые номера (от 0 до $k$). Некоторые прямоугольники объявляются «закрытыми» (это означает, что больше в них не будут вставляться квадраты), а остальные — «открытыми» (в любой открытый прямоугольник помещается ($k+1$)-й квадрат). Вначале «прямоугольником № 0» объявляется весь квадрат $\sqrt2\times\sqrt2$. Итак, алгоритм расстановки квадратов:
$k$-й шаг ($k=1$, 2, 3, $\ldots$). Выбираем из всех не закрытых прямоугольников тот, у которого наибольший номер. (Пусть этот номер — $m$.) Размещаем в его углу $k$-й квадрат. Продолжаем сторону этого квадрата, параллельную меньшей стороне прямоугольника $m$ (если стороны прямоугольника равны, выбираем любую из них) так, чтобы часть прямоугольника $m$, не занятая квадратом $k$, разбилась на два прямоугольника. Из этих двух прямоугольников мы присваиваем номер $k$ тому, который составляет прямоугольник вместе с квадратом $k$, а номер $m$ теперь сохраняем за оставшейся частью «бывшего» прямоугольника $m$ (рис. 4). За всеми квадратами и прямоугольниками, кроме прямоугольников $m$ и $k$, сохраняются старые номера. Если $k$-й квадрат, который мы разместили, — не последний, то проверим, помещается ли ($k+1$)-й квадрат в прямоугольник $k$ и в прямоугольник $m$, и если нет, то объявляем соответствующий прямоугольник (или оба) закрытым.
Рис. 4
(На рисунке 5 для примера показана возможная ситуация после 4-го шага. Для $k=5$ номер $m$ будет равен 2; бежевые прямоугольники закрыты.)
Нужно ещё доказать, что не может встретиться случай, когда окажутся закрытыми все прямоугольники, даже «номер 0». Прежде чем доказать это, заметим, что площадь закрытого прямоугольника номер $k$ меньше, чем площадь квадрата номер $k$ (это — основная идея нашего способа укладки!). Действительно, ясно, что до тех пор, пока меньшая сторона прямоугольника $k$ равна стороне квадрата $k$, он ещё не может быть закрыт (в него влезает даже $k$-й квадрат).
Рис. 5Рис. 6
Теперь предположим, что на некотором $n$-м шаге прямоугольник 0, который имел до этого шага размеры $c\times d$ ($c\ge d$), закрыт. Ясно, что на $n$-м шаге $m=0$, т. е. все прямоугольники с номерами $m\gt0$ закрыты, и их площадь меньше площади соответствующих квадратов.
Пусть $u$ и $v$ — стороны квадратов с номерами $n$ и $n+1$. Если квадрат $v\times v$ не помещается в прямоугольник $d\times(c-u)$ (рис. 6), то $v\ge c-u$, поэтому
$$
2(u^2+v^2)\ge(u+v)^2\ge c^2\ge cd,
$$
т. е. сумма площадей $n$-го и ($n+1$)-го квадратов не меньше половины площади прямоугольника $c\times d$. Получается, что уже первые $n+1$ квадратов составляют больше половины площади квадрата $\sqrt2\times\sqrt2$. Противоречие.
Предлагаем несколько задач, уточняющих и обобщающих утверждение задачи об упаковке квадратов.
Два равных квадрата со стороной $a$ нельзя разместить без пересечения в квадрате, сторона которого меньше $2a$.
Квадраты, сумма площадей которых равна $S$ и сторона наибольшего из которых равна $x$, можно упаковать в квадрат со стороной $x+\sqrt{S-x^2}$.
Эти квадраты можно упаковать в прямоугольник $a\times b$, если $a\ge x$, $b\ge x$ и $ab\ge2S$.
Если любую систему квадратов общей площадью 1 можно упаковать в прямоугольник $a\times b$, где $a\ge b$, то верно по крайней мере одно из двух условий:
$a\ge\sqrt3$ и $b\ge1$;
$a\ge\sqrt2$ и $b\ge\dfrac2{\sqrt3}$.
Д. Клейтман и М. Кригер доказали, что в прямоугольнике $1\times\sqrt3$ можно разместить любую систему квадратов общей площади 1. Правдоподобно, что аналогичное утверждение верно и для прямоугольника $\sqrt2\times\dfrac2{\sqrt3}$.
Прямоугольники, сумма площадей которых равна $S$ и наибольшая из сторон которых равна $x$, можно упаковать в прямоугольник $a\times b$, если $a\ge x$ и $ab\ge2S+\dfrac{a^2}8$.
Кубы общим объёмом $V$ можно упаковать в куб объёма $4V$.
