Can a finite number of squares, with total area at most 1, be fitted into a square with area 2?

Question

It seems to be a theorem that a finite number of squares, with total area at most 1, can be fitted into a square with area 2 without overlaps. I am looking for a proof of this.

Google led me to this mathoverflow answer (see Corollary 1). But I do not understand the answer -- in particular I cannot follow the proof of the "packing lemma" in the answer.

Can someone either explain the proof of the packing lemma given in that answer, or give another proof of it, or point me to any other proof of the question in the title?

Answer 1

This is the Moon-Moser Theorem, J W Moon and L Moser, Some packing and covering theorems, Colloq. Math. 17 1967 103–110, MR0215197 (35 #6040). It's also Problem 80 in Bela Bollobas, The Art of Mathematics; see pages 194-196 for the solution.

Janusz Januszewski, packing rectangles into the unit square, Geom Dedicata 81 (2000) 13-18, MR1772192 (2001d:52029) generalizes the result: every sequence of rectangles can be packed into the unit square provided their total area is at most $1/2$ and their side lengths are at most $1$.

Answer 2

The proof that you linked to is straightforward, but somewhat confusing, as they use $c$ to represent both the dimension of the original rectangle and the dimension of the largest remaining square. There is also, an overlooked case, as you have observed.

The idea of the proof is to use the induction hypothesis to cover more than $1/2$ of the area of smaller rectangles cut from $R$ until the remaining part of $R$ has area less than $c^2$, and noting that since the initial $c\times c$ subrectangle was completely covered more than half of $R$ is covered.

Here is an attempt to clarify the proof:

Packing Lemma. Let $R$ be a $c$ by $b$ rectangle, $c\le b$, and $F$ be a finite set of squares with the total area at least half the area of $R$ and the largest square of size $c$. Then a subset of $F$ containing the $c$ square can be packed into $R$ so that it covers at least half the area of $R$.

If $F$ contains only one square then the lemma is obviously true as we can fit into $R$ and it has more than half the area. So let us proceed by induction. First cut out a square of side $c$. Now let $c'$ be the largest square remaining. If it is possible to cut a strip of height $c'$ from the remainder of $R$ (making a rectangle of size $c\times c'$), do so. Now either the squares remaining in $F$ have area greater than half the strip, in which case we can cover more than half the strip with squares from $F$ by the induction hypothsis, then go back and cut another strip, etc., or the squares remaining have area less than half the area of the strip, in which case the we can fit them all into a sub rectangle having twice their area by the induction hypothesis, and we are done, as the total area of $F$ was at least half the area of $R$ and we have fit all the squares. When the largest remaining square is larger than the remainder of $R$ we are done. All of the strips except the last are more than half full, but the first square is completely full (it is the square of side $c$) and the remaining strip has less area than the square of side $c$ (it has width $c$ and height less than $c$) so the whole rectangle is over half covered.