3 rewrote, with the new proof of a more general result

I have rewritten the post so that the proof is correct.

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 suitable 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 Let R be an $a$ by $b$ rectangle with $b\leq a\leq 2b.$ Any set of squares of total area 1/2 at most $ab/2$ can be packed into a square of area 1R. (All rectangles and squares are assumed to be oriented parallel to the coordinate axes throughout.)

Corollary 1. A finite set of squares of total area 1 can be packed into a square of area 2.

Corollary 2. A finite set of circles of total area 1 can be packed into a circle of area 4.

Proof of Corollary 2. Order Replace each circle of diameter $d$ with a square of size $d$. Pack the squares by size starting from into a square of double their total area, then circumscribe a circle C around it. The inscribed circles of the largestsmall squares have given radii, disjoint interiors, and the area of C is four times the total area of the given circles. $\square$

Proof of Theorem. The theorem fairly easily follows from proof is by induction on the number of squares and uses the Packing Lemma below: just pack . Suppose that the squares largest square has size $c.$ Since $c^2\leq ab/2\leq b^2,$ we get $c\leq b.$ Split the rectangle R into vertical strips from left to two rectangles R' and R'' of the same height $b$ and of widths $c$ and $a-c$.

Case 1. If $c\leq a-b/2$ then the dimensions of the right making sure that rectangle R'' satisfy the conditions of the theorem, because $b/2\leq a-c\leq 2b.$ By the Packing Lemma, at least half the area of each vertical strip (except the last one) has been filledleft rectangle R' can be packed, starting with the $c$ square. The width of each strip is remaining squares are fewer in number and constitute at most half the size area of R''. By the largest unused squareinductive assumption, they can be packed into R''.

Case 2. If $c\geq a-b/2$ then $b\geq 2(a-c)$ and R'' contains a subrectangle R''' of height $2(a-c)$ and width $a-c$, to which is placed on topthe theorem applies. Pack the $c$ square into R'. Since $c^2+(a-c)^2\geq a^2/2\geq ab/2,$ the remaining squares have total area at most $(a-c)^2$ and can be packed into R''' by the inductive assumption. $\square$

Packing Lemma. Let R be an a $a$ c$by$b$rectangle,$a\leq c\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$. c$. Then a subset of F containing the $a$ c$square can be packed into R so that it covers at least half the area of R. The Packing Lemma is proved by induction Proof. Induction in the number of squares in F. The$a$by$b$Cut the rectangle R is successively cut into a sequence of horizontal strips of width$a$, c$, starting with the $a$ c$square at the topand at least half . The height of each subsequent strip , area-wise, is packed with squares from F, starting with the size of the largest unused square, which determines the height of the strip and is placed at the left (this is possible by end. By the inductive assumption)assumption, at least half of the strip, area-wise, can be packed with squares from F. The Continue the process is continued until the height of the remaining part of R ("the bottom strip") becomes less than$a$, c$, and hence its area less than $a^2.$ c^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 Comment: In the$a$square already. Otherwiseinitial post, let$c$be I said that the size of Packing Lemma easily implied the second largest square in F. Place it right below and flush left with result for packing 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 : order the smaller squares from F using recursion. Remove the top two strips by size and check whether successively apply the remaining part of R is taller than$a$: if yes, repeat with lemma to pack vertical columns whose widths are determined by the next size largest square from F, if not yet packed, stopstarting with the largest. EDIT:While striving to make the that argument as simple had virtues of simplicity and presentable as possiblepresentability, I've unfortunately made it had an unfortunate drawback of being invalid. If packing of the rectangles in the packing lemma stops right after the half the area has been covered then The columns are getting skinnier, so it may well happen that passing to the new vertical stripnext column, the largest remaining square is too wide to fitinto , even though its area is a tiny proportion of the outer squareremaining area. Specific example: if one attempts to pack the squares of sizes 1/2, 1/3, 1/6+$\epsilon$, 1/6+$\epsilon$, 1/6 into the square of size$2\sqrt{2}/3+\epsilon<1$following the naive algorithm then the first column has width 1/2 and contains the 1/2 square, the second column has width 1/3 and contains the next 3 squares (covering at least half the area in both cases), which leaves a narrow vertical strip of width less than 1/6 that cannot accommodate the remaining 1/6 square. I think that By controlling the argument can be salvaged by suitably strengthening distortion (the Packing Lemma, but this needs a careful thinking over ratio of width and I may not be able to do it for height), we get a few days (grading final exams takes precedence)more natural result. 2 accomodated the OP's change in formulation; added an explanation of a problem with the proof Theorem. A finite set of squares of total area 1 1/2 can be packed into a square of area 21. (All squares are assumed to be oriented parallel to the coordinate axes throughout.) 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. EDIT: While striving to make the argument as simple and presentable as possible, I've unfortunately made it invalid. If packing of the rectangles in the packing lemma stops right after the half the area has been covered then it may happen that passing to the new vertical strip, the largest remaining square is too wide to fit into the outer square. Specific example: if one attempts to pack the squares of sizes 1/2, 1/3, 1/6+$\epsilon$, 1/6+$\epsilon$, 1/6 into the square of size$2\sqrt{2}/3+\epsilon<1$following the algorithm then the first column has width 1/2 and contains the 1/2 square, the second column has width 1/3 and contains the next 3 squares (covering at least half the area in both cases), which leaves a narrow vertical strip of width less than 1/6 that cannot accommodate the remaining 1/6 square. I think that the argument can be salvaged by suitably strengthening the Packing Lemma, but this needs a careful thinking over and I may not be able to do it for a few days (grading final exams takes precedence). 1 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.