Circles In A Line

Been a month since I put up the circles puzzle last time, I guess its time to solve it out now.

Its easy to see that we lose nothing by just having all the circles in a line along the x-axis (say) and we will specify a circle by giving the distance between its center and the previous circle, we will call this d_i. Circle i will also have radius r_i, and we know r₀=1 from the setup (I'm numbering the circles 0 to 15 now, cause thats how I roll). The goal is to maximize d₁+d₂+d₃+...+d₁₅+r₁₅. Given d₁, r₁ gets specified, by d₁²+r₁²=1 (if this isn't clear to you, draw circles 0 and 1 and do some trig, its pretty simple). We can similarly see that d_i²+r_i²=r_i-1². So,

d₁²+r₁²=1
d₁²+d₂²+r₂²=1
d₁²+d₂²+d₃²+r₃²=1

And so on, until we have

Σd_i²+r₁₅²=1

As our restriction.

For some sense of completeness, we might as well add on a d₁₆ which equals r₁₅, and r₁₆ is zero. So we have to maximize Σd_i while holding Σd_i²=1. You probably just know this max is achived when the d_i are all equal, but lets solve it by Lagrange multipliers, because I haven't done that in years.

The maximum of f(x_i), subject to g(x_i)=K will occur at dg/dx_i=λdf/dx_i for each i. So, if f is the sum of x's and g is the sum of x²'s, we get x_i=λ/2, they are all the same, good.

Anwyay, so for our problem, this means that d_i=A, and since the sum of their squares is 1, they much each be 1/√16=1/4. Summing d_i to find the answer, we get 16/4, which is 4 for the maximum distance.

Its pretty easy to see that with N circles the answer will simply be √N, surprisingly fast asymptotically, but there you go.

When I told this problem to Sean, he suggested attempting the greedy algorithm. That is, just place the second circle to solve the two circle problem, and place the third circle to solve the local problem (which is a two circle problem again, but scaled down in size) and so on. Looking at the answer we got, its clear that the greedy algorithm won't work to give the optimal answer, but lets see what it does give.

The circles will again have radii given by r_i and the centers will be spaced a distance d_i from eachother. r₀=1 of course, and d₁ will be such that d₁+r₁ is maximized while d₁²+r₁²=1. So, we have d₁=1/√2=r₁. Next d₂ will be such that d₂+r₂ is maximized while d₂²+r₂²=1/2. So, we have d₂=1/√2²=r₂. Next d₃ will be such that d₃+r₃ is maximized while d₃²+r₃²=1/2². So, we have d₃=1/√2³=r₃.

Clearly we will get d_i=1/√2ⁱ=r_i, and the sum of the d_i will be the sum of 1/√2ⁱ. The infinite sum of aⁱ starting at 1 is a/(1-a), so when a=1/√2 we get 1/(√2-1) which is the same as 1+√2, so about 2.41. The greedy method asymptotes to a constant, neat.

Anyway, thats all I got.

Circles On Circles

New puzzle time? I guess it must be, its certainly not new solution time. Though I think I still have left that cats and dogs game hanging, one day I'll have to revisit that. Anyway, I found this puzzle on the xkcd forums, but its initially from the cofoundry:

There are 16 overlapping circles in a plane with the following proerties:
Circle 1 has radius 1
The diameter of circle 2 is a chord of circle 1
The diameter of circle 3 is a chord of circle 2
...
The diameter of circle 16 is a chord of circle 15
What is the maximum distance from a point in circle 16 to the center of circle 1?

By "overlapping circles" I really mean that circle N can share some interior points with circle N+1, it just helps to say it that way to imagine the setup. If you have forgotten your grade school geometry you may want to look up what a chord of a circle is on wikipedia or something.