## Chain of Circles

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

### Chain of Circles

Cosmologicon posted this puzzle on Confoundry, and it's one of my favorite puzzles on the site, so I thought I'd share it here. (My apologies if it's been posted already, but I didn't find it with my searches.) Surprisingly, only two people have solved it so far on that site.

Circle #0 has a radius of 1.

Circle #1 overlaps Circle #0. There is a chord of Circle #0 that is a diameter of Circle #1.

Circle #2 has a diameter that's a chord of Circle #1.

Circle #3 has a diameter that's a chord of Circle #2.

And so on up to Circle #15.

What's the largest possible value of the largest distance between a point on Circle #15 and the center of Circle #0?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

skeptical scientist
closed-minded spiritualist

Posts: 6135
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Chain of Circles

Spoiler:
31, assuming 'overlap' can mean 'share a single point,' and that circles 2 and up must overlap the one prior

The largest chord of a circle is its diameter. So, 15 circles of radius 1 = 30, plus the radius of circle 0.
redrogue

Posts: 119
Joined: Tue Dec 15, 2009 9:17 pm UTC

### Re: Chain of Circles

I think I have a solution:

Spoiler:
By rotational symmetry of circles, the optimal placement is to have all centres on a line.

If circle #n has radius rn and distance dn to the next circle (between centres), then we have the relationship rn2 = dn2 + rn+12 . Hence we have 1 = r02 = d02 + d12 + ... + d152 , where d15 = r15 is the distance from the centre of the last circle to its farthest point. We want to maximise d0 + d1 + ... + d15 . By AM-QM the maximum is attained for all d equal, i.e. d0 = d1 = ... = d15 = 1/4. The answer is 16*1/4 = 4.

Edit: Inserted sub and sup tags as suggested
Last edited by Pelli on Wed May 25, 2011 11:37 pm UTC, edited 1 time in total.
Pelli

Posts: 14
Joined: Fri Jun 26, 2009 6:02 am UTC

### Re: Chain of Circles

redrogue wrote:
Spoiler:
31, assuming 'overlap' can mean 'share a single point,' and that circles 2 and up must overlap the one prior

The largest chord of a circle is its diameter. So, 15 circles of radius 1 = 30, plus the radius of circle 0.

Circles sharing a single point overlap, but the diameter of one will not be a chord of the other, as required by the problem.

Pelli has the right solution, and a nice exposition as well (although you should really use [sub] and [sup] tags!)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

skeptical scientist
closed-minded spiritualist

Posts: 6135
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Chain of Circles

I'll just chime in and say that I thought the same way as redrogue and at least in my case the confusion comes from that I generally don't work with diameters as line segments but as a measure of the maximum distance between two points on the circle. Sure, if the latter meaning had been intended then the problem would not be well-phrased and it would be trivial (assuming that in such a case chord should've been length of a chord), but still.
Malle

Posts: 42
Joined: Wed Jan 07, 2009 1:50 pm UTC

### Re: Chain of Circles

Pelli wrote:I think I have a solution:

Spoiler:
By rotational symmetry of circles, the optimal placement is to have all centres on a line.

If circle #n has radius rn and distance dn to the next circle (between centres), then we have the relationship rn2 = dn2 + rn+12 . Hence we have 1 = r02 = d02 + d12 + ... + d152 , where d15 = r15 is the distance from the centre of the last circle to its farthest point. We want to maximise d0 + d1 + ... + d15 . By AM-QM the maximum is attained for all d equal, i.e. d0 = d1 = ... = d15 = 1/4. The answer is 16*1/4 = 4.

Edit: Inserted sub and sup tags as suggested
skeptical scientist wrote:Pelli has the right solution, and a nice exposition as well (although you should really use [sub] and [sup] tags!)

WOW!

Okay, I was the one who on counfoundry submitted four solutions, first one with a numeric answer, then when that was marked incorrect an explanation of my reasoning, and then after the hint was given, a different numeric answer, and then the explanation of the reasoning there.

(And for some reason even though that wasn't the answer, the solution was marked correct and then challenged which prevented me from attempting to solve it again for real this time ... I'm really annoyed at that since I would not have given up then)

I kept assuming the ratio of the diameters from each circle to the subsequent one in the series was constant, and although I removed that assumption for the ultimate circle, still kept it for the remaining circles, because I couldn't understand why it would be the case that if you were to maximize the ratio of the diameters for two circles, that wouldn't necessarily be optimal for a three-circle chain, and so on. Very nice puzzle and I'm still disappointed that I was just given the answer without continuing to have the chance to work it out myself.
Avin

Posts: 90
Joined: Sun Nov 25, 2007 3:08 am UTC

### Re: Chain of Circles

Avin wrote:I'm still disappointed that I was just given the answer without continuing to have the chance to work it out myself.
Pro-tip: don't click spoilers if you don't want to know the answer.
Moose Hole

Posts: 400
Joined: Fri Jul 09, 2010 1:34 pm UTC

### Re: Chain of Circles

Moose Hole wrote:
Avin wrote:I'm still disappointed that I was just given the answer without continuing to have the chance to work it out myself.
Pro-tip: don't click spoilers if you don't want to know the answer.

Avin

Posts: 90
Joined: Sun Nov 25, 2007 3:08 am UTC

### Re: Chain of Circles

Yeah, that's unfortunate. I'm not sure if it was me who did that, but I know I've accidentally done it elsewhere, usually because I start adding a comment, and then I forget to change it from correct to incorrect after I add the comment. Maybe I'll make a suggestion to address this issue.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

skeptical scientist
closed-minded spiritualist

Posts: 6135
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Chain of Circles

I was the one who mistakenly marked your answer correct. Really sorry about that, I could tell you were getting close. Was there a way I could have made it so you could answer again? I'm sorry, I couldn't figure it out.

I went and put in a feature request on the site to make it harder to accidentally mark answers correct, and also to be able to undo your own mistakes without approval from another judge. I don't know if that ever got implemented, I haven't been on the site in a while....

Cosmologicon

Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

### Re: Chain of Circles

Apropos of nothing, Confoundry has got some nice things going on in it. I guess the description didn't grab me when it was first described here.
Tirian

Posts: 1557
Joined: Fri Feb 15, 2008 6:03 pm UTC

### Re: Chain of Circles

I was initially very confused because I somehow interpreted it to mean that Circle #0's diameter was a chord of Circle #1, which (if I'm not mistaken) would mean that Circle #1 could be of any arbitrary size, thus making the answer infinite.

Anyway, it turns out the real answer involves basic geometry. I'm almost picturing it, but I'd love it if someone had a picture somewhere.

Lenoxus

Posts: 91
Joined: Thu Jan 06, 2011 11:14 pm UTC

### Re: Chain of Circles

Lenoxus wrote:Anyway, it turns out the real answer involves basic geometry. I'm almost picturing it, but I'd love it if someone had a picture somewhere.

Here you go:

Or, if you'd rather see all circles and the final point along a single line:

Mmmm, Geometer's Sketchpad is fun. It's kind of pricy, but you can play with it for 20 minutes at a time (no saving) without paying. I have no idea whether playing it will help solve the problem, but it's entirely possible.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

skeptical scientist
closed-minded spiritualist

Posts: 6135
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Chain of Circles

I went about it a bit differently:
Spoiler:
The solution, for any length of chain, is going to be equivalent up to scaling... that is, if you double the size of your initial circle, you just double the size of all the other circles, and your final distance is also doubled. Which means we can solve this recursively... if we know the ideal sizes for an n-1 chain, we can treat that as a unit and figure out how to scale it and position it on another circle, and end up with the ideal n chain.

The base case is the 1 chain, which obviously has a length of 1.

Now, say the n-1 chain has a length of L. To make an n chain, we have a unit circle, and then at a distance of x from that, we have the n-1 chain, and we need to find x. Now, the n-1 chain will be scaled down by sqrt(1-x2) to satisfy the chord-diameter thing, so the full length will be x + L*sqrt(1-x2). A quick differentiation finds that this is maximised when x = sqrt(1/(L2 + 1)). The n-1 chain will then be scaled down by a factor of sqrt(L2/(L2 + 1)). Substituting this back into our formula for the full length then gives sqrt(1/(L2+1)) + L*sqrt(L2/(L2+1)), which simplifies to just sqrt(L2+1). Given how simple this result is, there has to be a simpler way to derive it, but whatever, this works.

So, working from here, the maximal length of a 2 chain will be sqrt(2), the maximal length of a 3 chain will be sqrt(3), the maximal length of a 4 chain will be sqrt(4), etc. So the maximal length of the 16-chain will be sqrt(16) = 4.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6958
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Chain of Circles

skeptical scientist wrote:
Lenoxus wrote:I'm almost picturing it, but I'd love it if someone had a picture somewhere.

Here you go:

Excellent, thank you.

Lenoxus

Posts: 91
Joined: Thu Jan 06, 2011 11:14 pm UTC