13
$\begingroup$

Does there exist a family of discs $\lbrace D_{n}\rbrace_{n=1}^{\infty}$ in the Euclidean plane such that

  • the radius of $D_{n}$ is $\frac{1}{n+1}$,
  • each $D_{n}$ is contained in the unit disc, and
  • $D_{n}\cap D_{m} = \emptyset$ for each $n\neq m$ ?

(I'm not sure what tags are appropriate for this kind question, so if You have any suggestions, You're welcome to inform me about it via comments)

$\endgroup$
9
  • $\begingroup$ What is the source of this puzzle? $\endgroup$
    – Aryabhata
    Sep 15, 2010 at 20:58
  • 1
    $\begingroup$ @whuber: Please, read carefully the statement of the problem and You'll find the answer to Your question. I've only discovered that I shouldn't be able to pack them into a disk of radius smaller than $\sqrt{\pi^{2}/6−1}$ and I think it is not optimal bound (the better trivial bound is $5/6$). Please, correct me if I'm wrong. $\endgroup$
    – ifk
    Sep 15, 2010 at 22:28
  • 3
    $\begingroup$ There is a similar question at mathoverflow.net/questions/24184/… $\endgroup$
    – TonyK
    Sep 16, 2010 at 9:27
  • 1
    $\begingroup$ @TonyK: Thanks, although here we've got the ratio of areas $\approx 0.644934:1$, and concrete family of disks. In particular I hope this problem is easier. $\endgroup$
    – ifk
    Sep 16, 2010 at 9:55
  • 1
    $\begingroup$ @ifk: Fiktor's answer seems correct. Could you either say what part of your question is still open or accept one of the answers so the question gets marked as answered? $\endgroup$
    – joriki
    Sep 3, 2011 at 8:21

2 Answers 2

Reset to default
6
$\begingroup$

I think Apollonian circle packing is relevant here. It's certainly not identical with the question's topic, but it's enough to convince me that the answer is yes-- you can fit disks of radii 1/2, 1/3, 1/4,... inside a disk of radius 1. Hopefully someone more knowledgeable can make a rigorous argument, and solve the question for a disk of radius 5/6.

I found a paper on arXiv by Alex Kontorovich and Hee Oh demonstrating that for a bounded Apollonian circle packing, the number of circles with curvature at most N is asymptotic to cNa where a=1.30... This is good news for our problem! Apollonian packing greedily fits the largest possible circle in the gap created by any 3 mutually tangent circles, and the number of circles with radius at least 1/N grows as Na, where we just need it to grow as N.

Here is a picture from Wikipedia of an Apollonian packing, labeled by curvature (1/r): alt text

The outer circle has radius 1, and we want to find space for disks with curvature 2,3,4,5,... Compare the list of curvatures in the picture with the list we want to find space for:

2,2,3,3,6,6,6,6,11,11,11,11,14,14,14,14,15,15,18,18,18,18,23,23,23,23,26,26,26,26,27,27, 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,

27,27,30,30,30,30,35,35,35,35,35,35,38,38,38,38,38,38,38,38,... 34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,...

Everywhere the curvature in the lower list is $\geq$ the curvature in the upper list, we can just fit our disk inside the corresponding circle in the Apollonian packing. The only case in the list that doesn't fit is 10-- but since we've left unused space several times already, it's clear we can make room for it. Of course, shifting things to make room breaks the Apollonian packing (though we can leave three-quarters of it intact); but it sure looks like we have plenty of space left, and the asymptotic formula also suggests we are safe. I haven't looked closely at the paper for any explicit bounds that would make this rigorous. I realize it is just a sketch, but hopefully a convincing one.

The second Apollonian packing picture is analogous to the radius=5/6 case, scaled up 5x.
alt text

Here, we want to fit disks with curvature 10,15,20,25,30,35,40,45,50,... We run into trouble already with 30 (the disk of radius 1/6), and we'll have to shift things around quite a bit to fit our disks in. The Apollonian packing does not lead to a solution as easily as it seems to in the radius 1 case. Nonetheless, the asymptotic formula suggests that if we can pack the first N disks (for N perhaps not very large), that there will be plenty of room for the rest. One would have to work out some details to find the value of N.

$\endgroup$
1
5
$\begingroup$

The following is the rigorous construction of desired packing.

Consider the following picture:
alt text
On this picture discs with curvatures 2,2,3,3,6,6,6,6,11,11,11,11 are packed inside a unit disc. One can prove correctness of this image by solving quadratic equations. I want to cut circles with curvatures 2,3,4,5,6,... form these: use already obtained circles with curvatures 2 and 3. Use the second circle with curvature 2 for cutting 4,6,8,10,16,... (all even curvatures, starting with 4) using repeating the same procedure scaled to the circle with curvature 2. Use the second 3 for cutting 5 and 9. Use 6 for cutting 7. Use 11 for 11.

Now we have circles with radii 6, 6 and 6. Use the same procedure to obtain circles with curvatures 6*2, 6*3, 6*4, ... = 12, 18, 24, ... from them, each repeating 3 times. Use 12, 12 and 12 for 13, 15, 17; 18 for 19, 21, 23; 24 for 25, 27, 29 and so on.

One can check, that words "use the same procedure" are ok, because if we will use the scheme, described above to cut circles one by one (2, then 3, then 4, then 5, then 6, then 7 in this order) immediately repeating the steps in described smaller circles, we will never use result of the step before the step itself.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .