What is the smallest positive real $r\in\mathbb{R}$ with the following property?
Every finite collection of squares such that the sum of their areas equals $1$ can be arranged without overlap inside a square of area $r$
Asked
Active
Viewed 857 times
4
Dominic van der Zypen
- 45,374
-
2Why do you believe that there is such a number? Do you have an upper bound for it? – Dirk Apr 17 '18 at 09:01
-
@OP: The question is about the lower bound. There is no upper bound for this. – Georg Muehlenberg Apr 17 '18 at 14:16
-
(@GeorgMuehlenberg I think Dirk asked why an $r\in\mathbb{R}$ with the property above exists at all; this is addressed in the answer below.) – Dominic van der Zypen Apr 18 '18 at 06:03
1 Answers
11
First, it's easy to see that $r\geq \sqrt{2}$. The reason is that two squares of area 1/2 cannot fit in any smaller square.
This turns out to be sharp by a 1967 paper of Moon and Moser (see the discussion after Theorem 4 of "Some packing and covering theorems"). More generally, they show that any set of squares of total area $A$ (not even necessarily finite!) of which the largest has side $D$ can be packed into a square of side length $D+\sqrt{A-D^2}$.
They show this by giving a greedy algorithm for packing squares into a rectangle; first, one sorts the squares by size and then they start packing them into one row at the bottom of a square of side length $D+\sqrt{A-D^2}$. When the squares no longer fit in one row, one starts a second row above this one, and so on. Of course the key is proving some inequalities showing that this will always work.
See also On packing of squares and cubes by Meir and Moser (1968) which gives a more explicit proof and discusses the generalization of this result to higher dimensions.
There are quite a few variants which are still open and being studied. Here are two examples:
First is the question of the minimum number $A$ such that one can pack squares of total area 1 into some rectangle of area $\leq A$. See also "On packing squares into a rectangle" by Hougardy in 2011 which seems to be the best so far, showing $A\leq 2867/2048 \approx 1.3990$.
The MO question Can we cover the unit square by these rectangles? discusses a variation of this square-packing problem where one has the infinite set of $\frac{1}{k}\times\frac{1}{k+1}$ rectangles (the paper of Meir and Moser discusses this too).
Finally, note that the algorithm of Moon and Moser requires knowing the set of squares in advance (since one must sort by their size). There has been some work on the "online" version of this problem where squares are given one at a time and must be packed before the next one is given. The best result seems to be in this 2014 paper of Brubacher, which gives an algorithm achieving $r\leq 5/2$.
j.c.
- 13,490