Can an arbitrary collection of circles of total area 1/2 fit into a circle of area 1?

Question

Assume the circles are actually open disks, otherwise two circles each of area $\frac{1}{4}$ wouldn't fit into the circle of area 1.

This seems like it should be true, thinking about packing density, but I've not been able to find an algorithm that works in all cases.

Answer 1

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.

Theorem. Let R be an $a$ by $b$ rectangle with $b\leq a\leq 2b.$ Any set of squares of total area at most $ab/2$ can be packed into R. (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. Replace each circle of diameter $d$ with a square of size $d$. Pack the squares into a square of double their total area, then circumscribe a circle C around it. The inscribed circles of the small 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 proof is by induction on the number of squares and uses the Packing Lemma below. Suppose that the largest square has size $c.$ Since $c^2\leq ab/2\leq b^2,$ we get $c\leq b.$ Split the rectangle R into 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 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 the left rectangle R' can be packed, starting with the $c$ square. The remaining squares are fewer in number and constitute at most half the area of R''. By the inductive 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 the 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 a $c$ by $b$ rectangle, $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 $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.

Proof. Induction in the number of squares in F. Cut the rectangle R into a sequence of horizontal strips of width $c$, starting with the $c$ square at the top. The height of each subsequent strip is the size of the largest unused square, which is placed at the left end. By the inductive assumption, at least half of the strip, area-wise, can be packed with squares from F. Continue the process until the height of the remaining part of R ("the bottom strip") becomes less than $c$, and hence its area less than $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$

Comment: In the initial post, I said that the Packing Lemma easily implied the result for packing the square: order the squares by size and successively apply the lemma to pack vertical columns whose widths are determined by the largest square not yet packed, starting with the largest. While that argument had virtues of simplicity and presentability, it had an unfortunate drawback of being invalid. The columns are getting skinnier, so it may well happen that passing to the next column, the largest remaining square is too wide to fit, even though its area is a tiny proportion of the remaining 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. By controlling the distortion (the ratio of width and height), we get a more natural result.

Answer 2

It's still not a yes-or-no answer to your question, but it seems to be true that a collection of circles with area 1/9 can always fit into a circle of area 1. Or, more strongly, if the circles are placed largest-first, then no matter how the larger circles are placed (by a malicious adversary trying to prevent the packing from succeeding) there will always be room for each circle to be placed.

Proof sketch: as the circles are placed, maintain an "exclusion zone" where centers of new circles cannot go without potentially conflicting with existing circles. Initially, the exclusion zone covers the outer 1/3 of the radius of the area-1 circle, leaving 4/9 of its area free; with this initial exclusion zone, a circle with area at most 1/9 can have its center anywhere in the free area and not fall outside the boundary of the area-1 circle.

Then, when placing any circle, add to the exclusion zone a circular area with twice its radius; smaller circles whose centers are outside this zone cannot conflict with the placed circle.

If the total area of all circles is at most 1/9, then the total area of the exclusion zones formed in this way will always be less than 1, and there will always be a safe place for the center of the next circle to go.

Answer 3

After passions calmed down, I can put back my old unsuccessful attempt. At least I was quite enthusiastic at that time about the problem, until I have got downvotes and seen some vague ideas of others (they are still here) as answers.

Post as it was on May 12, 2010. Consider 3 circles of radii $r_1=r$, $r_2=2r$ and $r_3=3r$, where $r=1/(2\sqrt{7\pi})$, so that their total area $s$ is $$ s=\pi(r_1^2+r_2^2+r_3^2)=\frac12. $$

Descartes' theorem asserts that if three circles of radii $r_1$, $r_2$ and $r_3$ are pairwise externally tangent to each other and circumscribed by the circle of radius $R$, then $$ \frac1R=2\sqrt{\frac1{r_1r_2}+\frac1{r_2r_3}+\frac1{r_3r_1}} -\biggl(\frac1{r_1}+\frac1{r_2}+\frac1{r_3}\biggr). $$ In our case we find from this formula that $$ R=\frac3{\sqrt{7\pi}}, $$ so that the area $S$ of the circumscribing circle is $$ S=\pi R^2=\frac97>1. $$ This implies that the three given circles of total area $1/2$ cannot be put inside a circle of total area 1 without intersections.

Edit. I have to agree that my geometric intuition is too weak to notify an obvious non-applicability of Decartes' theorem. As Tony mentions in his comment, one can fit these three circles in a circle of radius $r_2+r_3$, and the circle of radius $r_1$ fits in one of the gaps, without touching the enclosing circle.

Without trying to correct the above solution I indicate another choice: $r_1=0.99q$, $r_2=r_3=2q$, where $q$ is chosen in such a way that the total area is again $1/2$. Decartes' theorem produces the circumscribing circle of area $>1.008$. There is still an option to put two large circles along a diameter of circle of total area 1 and see whether there is a room for the smaller one. This definitely means that more geometry is involved...

Final edit (hopefully). As Roland mentions, the three circles again fit a circle of radius $r_2+r_3$. After the two large equal circles are inscribed, there is a room for another circle of radius $2r_2/3$ (well, one can still have the space for the other of radius $2r_3/3$, but I do not care of more than 3 circles inscribed). The corresponding geometric picture involves the right triangles with sides $1$, $4/3$, and $5/3$, a nice appearance of the Pythagorean triple $3^2+4^2=5^2$.

Is it true that this ($r_1=2/3$, $r_2=r_3=1$, total area $s=22\pi/9$) is the worth case of inscribing 3 circles into the circle of radius $R=2$ (area $S=4\pi$)? The quality of this inscription is $S/s=18/11$. In other words, can we replace areas $1/2$ and $1$ in the original problem by $11/18$ and $1$ respectively, if at least three circles are inscribed?

I have to apologize for my unsuccessful attempt. You still have a chance to enjoy the beauty and difficulty of the original problem. I thank Tony and Roland for pointing out my mistakes in geometry.

Answer 4

After weeks of sweating through computations without success, I think I have an auxillary result which I can use to tackle the problem posted above. However, the path to the conclusion is so surprising that I invite verification, in particular to point out any show-stopper mistake that may or may not be lurking.

The auxillary result involves a region that is the "suitcase" circle with a segment removed. Let C be a disk of radius 1, and draw a chord of C which has distance 1/2 from the center of C. Let D be that part of C (including the chord itself) that is on the same side of the chord as the center of C, so D is a disk with a segment chopped off so that the area of D is less than 5/6 the area of C. Let F and G be two closed disks with unequal radii whose areas sum to half the area of C.

Result: F and G pack inside D.

Note that if F and G have the same radius, they will not pack inside D for the same reason they won't pack inside C: they have to share a point which is the circle center.

The proof of the result involves placing F and G so that they touch the chord and otherwise are as far apart inside D as possible. The analogous problem for packing inside C involves placing F and G inside C so that the centers of F, G, and C are on the same line and F and G are as far apart as possible, then use the area sum condition to show the radii of F and of G sum to less than 1, and so they can be pushed together just enough to remain disjoint and keep away from the region boundary.

For the result about D, I orient the coordinates to have the chord parallel to the x axis, and then I show that the x coordinates of the centers of F and G are greater than distance 1 apart. It took me weeks to realize that was what was needed to be shown. Even so, the algebra involved led to a surprise, which I want someone else to confirm or deny.

Now for the algebraic verification. Let $0 \leq s \lt 1/2 \lt r \leq \sqrt{1/2}$ where $s$ and $r$ are the lengths of the radii of F and G. The area sum condition yields $r^2 + s^2 = 1/2$, and the inequality to be shown is inequality (A): $\sqrt{3/4 - r} + \sqrt{3/4 - s} \gt 1$. Since this inequality on the x coordinates of the centers of F and G imply that F and G are disjoint, inequality (A) will yield the result.

There may be a slick analytic way to show (A), but I use repeated squaring and rearrangments to yield a quartic polynomial in $r$. I start by writing $s$ as $\sqrt{1/2 - r^2}$ and isolate the radical with $s$ on one side, and square both sides. I end up with an inequality to prove that has $\sqrt{1/2 - r^2}$ as a subexpression, and so I isolate the summand containing that subexpression on one side and square again.

I collect and rearrange and square again to get the following inequality to be shown: $49/4 - 42r + 50r^2 - 24r^3 + 4r^4 \gt (1 - 2r + r^2)(12 - 16r)$. I then collect terms and decide to factor out a term of $(r - 1/2)$ in hopes of getting an easier polynomial to handle to show that it is positive for $r$ in the range given above. I know the relations above yield 0 when $r$ is $1/2$, so it seems like a nice simplification.

The surprise comes when I find out the above inequality is equivalent to (B): $4(r - 1/2)^4 \gt 0$. I was not expecting that at all! If I have it right, then the result is proved, and I can move on after weeks of fruitless labor involving delta and epsilons and sketches that had no $r$'s or $s$'s. Can someone rederive or otherwise prove inequality A above? Even better, can someone tell me how I could know inequality B was coming?

Gerhard "Surprised After All These Weeks" Paseman, 2012.05.07

Answer 5

This is not at all a complete answer but a remark which can be improved. It is a completely rewritten and replaces bullshit (explaining the first comments.)

Suppose the answer to Segerman's question is no. There exists thus a counterexample given by a decreasing sequence $r_1\geq \dots \geq r_n$ of radii such that $\sum_{i=1}^n r_i^2=1/2$ and one can not fit $n$ circles with radii $r_1,\dots,r_n$ into a circle $C_1$ of radius $1$. Suppose $n$ is the smallest integer for which a counterexample exists. Then $r_1<2/3$. Indeed, the area $\pi(1/2-r_1^2)$ of the discs of radii $r_2,\dots,r_n$ is at most half the area $\pi(1-\rho_1)^2$ of the largest disc $C'$ which fits together with the disc $C_1$ of radius $r_1$ into $C$. Since $n$ is minimal, the $(n-1)$ circles of radii $r_2,\dots,r_n$ can be packed into $C'$.

This kind of argument can be improved (pack the circles of radii $r_2,\dots$ into more than one circle of suitable radii which fit into $C$ together with $ C_1$) in order to lower the upper bound on the largest radius of a minimal counterexample.

I guess one can use a packing argument showing that a solution always exists if the largest radius is small enough.

These two bounds can perhaps be made to met (but I fear that the involved combinatorics are quite messy).

Let me make the argument for small radii a little bit more (but not entirely, I agree that some more work is needed) rigorous. (This is probably similar to the argument suggested by fedja (see comment below), I admit that I do not quite understand the details).

Supposing the total area of all discs of radius $\leq \epsilon$ exceeds $2\pi \epsilon$, look at the annulus of width $\epsilon$ and outer radius $1$ inside the large disc, supposed to be of radius $1$. If $\epsilon$ is very small, such an annulus looks locally like a strip delimited by two parallel lines at distance $\epsilon$. I have thus to prove that given a collection of radii $\leq 1/2$, I can cover more than half of the area of a very long strip delimited by two parallel lines at distance $1$.

If all discs have equal radius, then I can cover asymptotically a proportion of at least $\pi/4\sim .7854$ of the strip (the least favorable case corresponds to a collection of discs all of maximal radius $1/2$). The general case should be better but is harder to analyze. I claim however that this analysis can be made. Indeed, up to subdividing the strip into smaller substrips, we can assume that all radii are $>1/4$ and we have then a fairly small number of combinatorial situations to consider. We can thus compute the worst case.