Chain of Circles

[skeptical scientist]

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?

[redrogue]

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.

[Pelli]

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 r_n and distance d_n to the next circle (between centres), then we have the relationship r_n² = d_n² + r_n+1² . Hence we have 1 = r₀² = d₀² + d₁² + ... + d₁₅² , where d₁₅ = r₁₅ is the distance from the centre of the last circle to its farthest point. We want to maximise d₀ + d₁ + ... + d₁₅ . By AM-QM the maximum is attained for all d equal, i.e. d₀ = d₁ = ... = d₁₅ = 1/4. The answer is 16*1/4 = 4.

Edit: Inserted sub and sup tags as suggested

[skeptical scientist]

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!)

[Malle]

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.

[Avin]

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 r_n and distance d_n to the next circle (between centres), then we have the relationship r_n² = d_n² + r_n+1² . Hence we have 1 = r₀² = d₀² + d₁² + ... + d₁₅² , where d₁₅ = r₁₅ is the distance from the centre of the last circle to its farthest point. We want to maximise d₀ + d₁ + ... + d₁₅ . By AM-QM the maximum is attained for all d equal, i.e. d₀ = d₁ = ... = d₁₅ = 1/4. The answer is 16*1/4 = 4.

Edit: Inserted sub and sup tags as suggested

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.

[Moose Hole]

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]

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.

I'm not talking about this forum. I already knew the answer when someone incorrectly marked my answer correct on TheConfoundry.

[skeptical scientist]

I'm not talking about this forum. I already knew the answer when someone incorrectly marked my answer correct on TheConfoundry.

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.

[Cosmologicon]

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....

[Tirian]

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.

[Lenoxus]

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.

[skeptical scientist]

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.

[phlip]

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-x²) to satisfy the chord-diameter thing, so the full length will be x + L*sqrt(1-x²). A quick differentiation finds that this is maximised when x = sqrt(1/(L² + 1)). The n-1 chain will then be scaled down by a factor of sqrt(L²/(L² + 1)). Substituting this back into our formula for the full length then gives sqrt(1/(L²+1)) + L*sqrt(L²/(L²+1)), which simplifies to just sqrt(L²+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.

[Lenoxus]

I'm almost picturing it, but I'd love it if someone had a picture somewhere.

Here you go:

Excellent, thank you.