Chain of Circles

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Prelates, Moderators General

Chain of Circles

Postby skeptical scientist » Wed May 25, 2011 6:24 pm UTC

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
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6149
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Chain of Circles

Postby redrogue » Wed May 25, 2011 6:54 pm UTC

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.
Is 'no' your answer to this question?
redrogue
 
Posts: 119
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Chain of Circles

Postby Pelli » Wed May 25, 2011 7:10 pm UTC

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

Postby skeptical scientist » Wed May 25, 2011 11:24 pm UTC

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
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6149
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Chain of Circles

Postby Malle » Thu May 26, 2011 8:38 am UTC

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

Postby Avin » Fri May 27, 2011 3:18 pm UTC

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: 91
Joined: Sun Nov 25, 2007 3:08 am UTC

Re: Chain of Circles

Postby Moose Hole » Fri May 27, 2011 4:28 pm UTC

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

Postby Avin » Fri May 27, 2011 5:38 pm UTC

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.


I'm not talking about this forum. I already knew the answer when someone incorrectly marked my answer correct on TheConfoundry.
Avin
 
Posts: 91
Joined: Sun Nov 25, 2007 3:08 am UTC

Re: Chain of Circles

Postby skeptical scientist » Fri May 27, 2011 5:45 pm UTC

Avin wrote: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.
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
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6149
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Chain of Circles

Postby Cosmologicon » Mon Jun 13, 2011 6:29 pm UTC

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....
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Re: Chain of Circles

Postby Tirian » Tue Jun 14, 2011 3:28 pm UTC

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: 1589
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Chain of Circles

Postby Lenoxus » Tue Feb 14, 2012 10:52 pm UTC

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.
User avatar
Lenoxus
 
Posts: 110
Joined: Thu Jan 06, 2011 11:14 pm UTC

Re: Chain of Circles

Postby skeptical scientist » Thu Feb 16, 2012 5:00 am UTC

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:
Image

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

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
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6149
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Chain of Circles

Postby phlip » Thu Feb 16, 2012 6:46 am UTC

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.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7146
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Chain of Circles

Postby Lenoxus » Fri Feb 17, 2012 7:46 pm UTC

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.
User avatar
Lenoxus
 
Posts: 110
Joined: Thu Jan 06, 2011 11:14 pm UTC


Return to Logic Puzzles

Who is online

Users browsing this forum: Bing [Bot] and 5 guests