Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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$.

share|improve this answer
    
Thanks Gerry. [blah] –  Kevin Buzzard Feb 15 '12 at 7:53

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.

share|improve this answer
    
You seem to have just reproduced the proof in the link. Can you clarify the bit I don't understand, which is "do so and fill more than half of it with squares from $F$, this is possible by the induction hypothesis"? I don't see why we know $F$ minus the square of side length $c$ is guaranteed to have area at least half of the $c\times c'$ rectangle -- this is precisely the part of the argument I don't follow. –  Kevin Buzzard Feb 15 '12 at 7:33
    
Perhaps I should be even more blunt. Consider the case where there are two squares, side lengths 1 and 0.1, and we're trying to fit them into a rectangle with sides 1 and 2.02. Sure we can do this, but the algorithm that is given in your answer seems to me to fail, because when we've put the unit square in, the remainder still has area more than the unit square so we're not done, and we don't have enough squares to fill more than half of the $1\times 0.1$ rectangle either, so the algorithm you give seems to me to fail as it stands even though the result is fine in this case. –  Kevin Buzzard Feb 15 '12 at 7:59
    
@KevinBuzzard You are correct, I missed that case (as did the other post. In the case that you do not have enough area left in $F$ to cover half the strip, then by the induction hypothesis you can use all your rectangles to cover half of a sub rectangle of your strip, thereby using all of $F$ and covering half of $R$ by the hypothesis of the theorem (the total area of $F$ is more than twice the area of $R$) –  deinst Feb 15 '12 at 12:30
    
@KevinBuzzard to do your example, we fit the 1x1 square, then make a strip of height 0.1, cut a 0.1 x 0.2 rectangle from it, fit the remaining rectangle, and we are done. –  deinst Feb 15 '12 at 12:35
    
Yes -- now I see what I was missing in Victor's answer. Thanks a lot! –  Kevin Buzzard Feb 15 '12 at 20:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.