# Putting many disks in the unit square

Consider a square of side equal to $1$. Prove that we can place inside the square a finite number of disjoint circles, with different radii of the form $1/k$ with $k$ a positive integer, such that the area of the remaining region is at most $0.0001$.

If we consider all the circles of this form, their total area is $\sum_{k \geq 1}\displaystyle \pi \frac{1}{k^2} - \pi=\frac{\pi^3}{6}-\pi\simeq 2.02$ which is greater than the area of the square. (I subtracted $\pi$ because we cannot place a disk of radius $1$ inside the square).

So the circles of this form can cover the square very well, but how can I prove that there is a disjoint family which leaves out a small portion of the area?

-
What is this question from? I've come across it before, but I don't remember where? –  mixedmath Aug 13 '11 at 6:34
@Mike: This time the radii are supposed to be of the form $1/k$, AND they are supposed to be distinct. –  Jyrki Lahtonen Aug 13 '11 at 7:38
@Beni: Well, you're not alone. In French, for example, it's called "soustraction" with an s, so Frenchmen also often make this mistake in English. –  Hans Lundmark Aug 13 '11 at 10:20
@user1551: I got it from an old geometry book, where the constant is $0.0001$, but I guess there is nothing special about this constant and the remaining area could be made as small as we need. –  Beni Bogosel Aug 13 '11 at 14:51
It's like pulling teeth! But I found it: "Probleme de geometrie elementară", Editura Didactică şi Pedagogică, Bucharest, 1979. –  TonyK Sep 3 '11 at 9:45

I don't think this is possible for general $\epsilon$, and I doubt it's possible for remainder $0.0001$.

Below are some solutions with remainder less than $0.01$. I produced them by randomized search from two different initial configurations. In the first one, I only placed the circle with curvature $2$ in the centre and tried placing the remaining circles randomly, beginning with curvature $12$; in the second one, I prepositioned pairs of circles that fit in the corners and did a deterministic search for the rest.

The data structure I used was a list of interstices, each in turn consisting of a list of circles forming the interstice (where the lines forming the boundary of the square are treated as circles with zero curvature). I went through the circles in order of curvature and for each circle tried placing it snugly in each of the cusps where two circles touch in random order. If a circle didn't fit anywhere, I discarded it; if that decreased the remaining area below what was needed to get up to the target value (in this case $0.99$), I backtracked to the last decision.

I also did this without using the circle with curvature $2$. For that case I did a complete search and found no configurations with remainder less than $0.01$. Thus, if there is a better solution in that case, it must involve placing the circles in a different order. (We can always transform any solution to one where each circle is placed snugly in a cusp formed by two other circles, so testing only such positions is not a restriction; however, circles with lower curvature might sit in the cusps of circles with higher curvature, and I wouldn't have found such solutions.)

For the case including the circle with curvature $2$, the search wasn't complete (I don't think it can be done completely in this manner, without introducing further ideas), so I can't exclude that there's are significantly better configurations (even ones with in-order placement), but I'll try to describe how I came to doubt that there's much room for improvement beyond $0.01$, and particularly that this can be done for arbitrary $\epsilon$.

The reasons are both theoretical and numerical. Numerically, I found that this seems to be a typical combinatorial optimization problem: There are many local minima, and the best ones are quite close to each other. It's easy to get to $0.02$; it's relatively easy to get to $0.011$; it takes quite a bit more optimization to get to $0.01$; and beyond that practically all the solutions I found were within $0.0002$ or so of $0.01$. So a solution with $0.0001$ would have to be of a completely different kind from everything that I found.

Now of course a priori there might be some systematic solution that's hard to find by this sort of search but can be proved to exist. That might conceivably be the case for $0.0001$, but I'm pretty sure it's not the case for general $\epsilon$. To prove that it's possible to leave a remainder less than $\epsilon$ for any $\epsilon\gt0$, one might try to argue that after some initial phase it will always be possible to fit the remaining circles into the remaining space. The problem is that such an argument can't work, because we're trying to fill the rational area $1$ by discarding rational multiples of $\pi$ from the total area $\pi^3/6$, so we can't do it by discarding a finite number of circles, since $\pi$ is transcendental.

Thus we can never reach a stage where we could prove that the remaining circles will exactly fit, and hence every proof that proves we can beat an arbitrary $\epsilon$ would have to somehow show that the remaining circles can be divided into two infinite subsets, with one of them exactly fitting into the remaining gaps. Of course this, too, is possible in principle, but it seems rather unlikely; the problem strikes me as a typical messy combinatorial optimization problem with little regularity.

A related reason not to expect a clean solution is that in an Apollonian gasket with integer curvatures, some integers typically occur more than once. For instance, one might try to make use of the fact that the curvatures $0$, $2$, $18$ and $32$ form a quadruple that would allow us to fill an entire half-corner with a gasket of circles of integer curvature; however, in that gasket, many curvatures, for instance $98$, occur more than once, so we'd have to make exceptions for those since we're not allowed to reuse those circles. Also, if you look at the gaskets produced by $0$, $2$ and the numbers from $12$ to $23$ (which are the candidates to be placed in the corners), you'll find that the fourth number increases more rapidly than the third; that is, $0$, $2$ and $18$ lead to $32$, whereas $0$ $2$ and $19$ already lead to $(\sqrt2+\sqrt{19})^2\approx33.3$; so not only can you not place all the numbers from $12$ to $23$ into the corners (since only two of them fit together and there are only four corners), but then if you start over with $24$ (which is the next number in the gasket started by $12$), you can't even continue with the same progression, since the spacing has increased. The difference would have to be compensated by the remaining space in the corners that's not part of the gaskets with the big $2$-circle, but that's too small to pick up the slack, which makes it hard to avoid dropping several of the circles in the medium range around the thirties.

My impression from the optimization process is that we're forced to discard too much area quite early on; that is, we can't wait for some initial irregularities to settle down into some regular pattern that we can exploit. For instance, the first solution below uses all curvatures except for the following: 3 4 5 6 7 8 9 10 11 16 17 20 22 25 30 31 33 38 46 48 49 52 53 55 56 57 59 79 81 94 96 101 106 107 108 113 125 132. Already at 49 the remaining area becomes less than would be needed to fill the square. Other solutions I found differed in the details of which circles they managed to squeeze in where, but the total area always dropped below $1$ early on. Thus, it appears that it's the irregular constraints at the beginning that limit what can be achieved, and this can't be made up for by some nifty scheme extending to infinity. It might even be possible to prove by an exhaustive search that some initial set of circles can't be placed without discarding too much area. To be rigorous, this would have to take a lot more possibilities into account than my search did (since the circles could be placed in any order), but I don't see why allowing the bigger circles to be placed later on should make such a huge difference, since there's precious little wiggle room for their placement to begin with if we want to fit in most of the ones between $12$ and $23$.

So here are the solutions I found with remainder less than $0.01$. The configurations shown are both filled up to an area $\gtrsim0.99$ and have a tail of tiny circles left worth about another $0.0002$. For the first one, I checked with integer arithmetic that none of the circles overlap. (In fact I placed the circles with integer arithmetic, using floating-point arithmetic to find an approximation of the position and a single iteration of Newton's method in integer arithmetic to correct it.)

The first configuration has $10783$ circles and was found using repeated randomized search starting with only the circle of curvature $2$ placed; I think I ran something like $100$ separate trials to find this one, and something like $1$ in $50$ of them found a solution with remainder below $0.01$; each trial took a couple of seconds on a MacBook Pro.

The second configuration has $17182$ circles and was found by initially placing pairs of circles with curvatures $(12,23)$, $(13,21)$, $(14,19)$ and $(15,18)$ touching each other in the corners and tweaking their exact positions by hand; the tweaking brought a gain of something like $0.0005$, which brought the remainder down below $0.01$. The search for the remaining circles was carried out deterministically, in that I always tried first to place a circle into the cusps formed by the smaller circles and the boundary lines; this was to keep as much contiguous space as possible available in the cusps between the big circle and the boundary lines.

I also tried placing pairs of circles with curvatures $(13,21)$, $(14,19)$, $(15,18)$ and $(16,17)$ in the corners, but only got up to $0.9896$ with that.

Here are high-resolution version of the images; they're scaled down in this column, but you can open them in a new tab/window (where you might have to click on them to toggle the browser's autoscale feature) to get the full resolution.

Randomized search:

With pre-placed circles:

-
That's a bit crazy. Very crazy. But very pretty, too, in a way. –  mixedmath Sep 11 '11 at 18:52
This is amazing (+1)! Can you reveal some details about the implementation and the effort? –  Jiri Sep 11 '11 at 19:11
+1. Wow! So the problem is (almost) correct, but it can't be solved using only math.... :) Nice work! –  Beni Bogosel Sep 11 '11 at 19:21
@Jiri: done :-) –  joriki Sep 11 '11 at 21:08
This would have made a great Project Euler Problem :) –  Beni Bogosel Sep 12 '11 at 10:51
show 1 more comment

Let's roll up our sleeves here. Let $C_k$ denote the disk of radius $1/k$. Suppose we can cover an area of $\ge 0.9999$ using a set of non-overlapping disks inside the unit square, and let $S$ denote the set of integers $k$ such that $C_k$ is used in this cover.
Then we require

$$\sum_{k\in S}\frac{1}{k^2} \ge 0.9999/\pi \approx 0.318278$$

As the OP noted, we know that $1 \not\in S$. This leaves

$$\sum_{k\ge2}\frac{1}{k^2} \approx 0.644934$$

which gives us $0.644934 - 0.318278 = 0.326656$ 'spare capacity' to play with.

Case 1 Suppose $2 \in S$. Then the largest disk that will fit into the spaces in the corners left by $C_2$ is $C_{12}$, so we must throw $3,...,11$ out of $S$. This wastes

$$\sum_{k=3}^{11}\frac{1}{k^2}\approx0.308032$$

and we are close to using up our spare capacity: we would be left with $0.326656-0.308032=0.018624$ to play with.

Case 2 Now suppose $2 \not\in S$. Then we can fit $C_3$ and $C_4$ into the unit square, but not $C_5$. So we waste

$$\frac{1}{2^2} + \frac{1}{5^2} = 0.29$$

leaving us with $0.326656-0.29=0.036656$ to play with.

Neither of these cases fills me with confidence that this thing is doable.

-
Things get a lot better after the waste from 3 to 11. I've got up to 0.989; will be posting some results shortly; but I also suspect that 0.9999 may not be doable. –  joriki Sep 7 '11 at 17:16
@joriki: Can you present, please how you got to $0.989$? Thank you. –  Beni Bogosel Sep 9 '11 at 19:31
@Beni: I will shortly. –  joriki Sep 9 '11 at 20:19
@joriki, I think you can get to 0.9999 even in Case 1. You place $C_2$, then $C_{12}$ through $C_{15}$ in the corners. Tangent to $C_{12}$ and $C_2$ you place $C_{25}$ and $C_{24}$, then tangent to 24 and $C_2$ you place $C_{40}$ and in general you can place $2n(n-1)$ tangent to the previous one and $C_2$. You do the same in the other corners, starting with $C_{23}$ and $C_{26}$ by $C_{13}$, $C_{22}$ and $C_{27}$ by $C_{14}$ and $C_{21}$ and $C_{28}$ by $C_{15}$. Summing these series gets you pretty close to the number you're looking for, and you are left with plenty of gaps for circles. –  Craig Sep 10 '11 at 3:23
@Craig: The problem isn't so much the gaps left for circles but the circles left for gaps :-) –  joriki Sep 10 '11 at 6:16
show 1 more comment

I suggest the following idea: Look at http://en.wikipedia.org/wiki/Descartes%27_theorem and in particular the Special cases. Show inductively that all curvatures remain integers as in http://en.wikipedia.org/wiki/Apollonian_gasket. Now place some well chosen circles into the square and maybe fill up into the corners (as filling between a corner and a circle is not handled with Decartes). All other areas, i.e. in between circles and between circles and square edges you can fill with the Decartes theorem. You can probably show analytically which radii you are going to use up. Now sum their areas.

-
Although I am not the OP, I have become very interested in the problem. I toyed briefly with Descartes, and I'm having a very hard time coming up with anything particular. I was wondering if you had thought any more on the problem and had a more complete solution in mind, or if this sort of intuitive line or reasoning was all that you'd come up with so far? –  mixedmath Sep 6 '11 at 3:32
No, sorry, I don't have a precise solution in mind. I just hope that if you place the initial circles correctly, you will be able to prove that all subsequent circles squeezed in between, will be distinct (maybe due to some invariant like modules arithmetics). This series of circles might be calculable in closed form and then summed. But this is just a guess. ATM I don't have much time to think further :( –  Gerenuk Sep 6 '11 at 9:11
I would suspect that you could do a computer search, given that you do have a finite (and quite large) cutoff of 0.0001. That means you hopefully only have to place circles with radius up to a small multiple of 100. Start by placing the circles that are tangent to 2 or more sides by hand, then searching on the remainder. –  Craig Sep 6 '11 at 15:22
I guess using computer search would be very easy. Just use Decartes and a greedy algorithm until you fill the space. Maybe its all easier, if you can proof that for whatever little space is left, you can always fit an a circle and this way the upper bound on the filling ratio is not below 1. Of course you have to keep in mind the different sizes of the circles. –  Gerenuk Sep 6 '11 at 16:00
@Gerenuk: If it's very easy, why haven't you tried it? I think you might change your mind.... –  TonyK Sep 7 '11 at 17:51
show 1 more comment