Skip to main content
1 of 3
Victor Protsak
  • 14.5k
  • 4
  • 68
  • 94

This problem is a bit hard, but following the Polya dictum, here is the answer to an apparently easier one: yes, if circles are replaced with parallel squares, and moreover, a version of the greedy algorithm works. (I must confess that I've spent quite a bit of time arriving at the solution, even if in retrospective it looks rather obvious.)

Theorem. A finite set of squares of total area 1 can be packed into a square of area 2. (All squares are assumed to be oriented parallel to the coordinate axes throughout.)

Proof. Order the squares by size starting from the largest. The theorem fairly easily follows from the Packing Lemma below: just pack the squares into vertical strips from left to right making sure that at least half the area of each vertical strip (except the last one) has been filled. The width of each strip is the size of the largest unused square, which is placed on top.

Packing Lemma. Let R be an $a$ by $b$ rectangle, $a\leq 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 $a$. Then a subset of F containing the $a$ square can be packed into R so that it covers at least half the area of R.

The Packing Lemma is proved by induction in the number of squares in F. The $a$ by $b$ rectangle R is successively cut into horizontal strips of width $a$, starting with the $a$ square at the top and at least half of each subsequent strip, area-wise, is packed with squares from F, starting with the largest unused square, which determines the height of the strip and is placed at the left (this is possible by the inductive assumption). The process is continued until the height of the remaining part of R ("the bottom strip") becomes less than $a$, and hence its area less than $a^2.$ At this point at least half of the area of the intermediate strips has been covered, as well as the larger of the areas of the top and the bottom strip, so that at least half of R has been covered. $\square$

Here is a more algorithmic description of the packing. If $b-a\leq a$ then at least half the area of R has been covered by the $a$ square already. Otherwise, let $c$ be the size of the second largest square in F. Place it right below and flush left with the $a$ square, the second horizontal strip is a rectangle of width $a$ and height $c$. At least half of this rectangle can be packed by the smaller squares from F using recursion. Remove the top two strips and check whether the remaining part of R is taller than $a$: if yes, repeat with the next size square from F, if not, stop.

Victor Protsak
  • 14.5k
  • 4
  • 68
  • 94