Circles Puzzle

[henryzz]

Some very interesting solutions here. I expected the needed number of circles to rise much faster than it has. There is a surprising amount of symmetry in the solutions as well.
@Robert Was this the limit of your program or the limit of how many solutions you wanted to post?
If your program does further I would be interested in a list of how many circles are needed for each size.

[R. Gerbicz]

Originally Posted by henryzz

Some very interesting solutions here. I expected the needed number of circles to rise much faster than it has. There is a surprising amount of symmetry in the solutions as well.
@Robert Was this the limit of your program or the limit of how many solutions you wanted to post?
If your program does further I would be interested in a list of how many circles are needed for each size.

First there was a limit of n=8 in my code (8^2=64 so I could store every offset in an unsigned long long int), now I have a limit of n=16 (but now it is easy to increase this). First not thought that I can reach n=8.

After some search found that this is a known problem (but still was not in oeis), see http://web.archive.org/web/200107221...riedma/cirpts/

I have reached this yesterday, see my solutions for n=11 and n=12. The sequence now submitted to oeis, the draft is at: https://oeis.org/draft/A262355.

[R. Gerbicz]

a(n)=O(n^2/sqrt(log(n))) is true, the proof is not that hard, see on oeis.

See the probably non-optimal solutions for n=13,14 (these are using at most one more circle than the optimal solution,
so a(13)=18 or 19, and a(14)=19 or 20).

[LaurV]

I think* a13=19 is the right, and "almost" I can prove the 18 circles are not enough. What intrigued me, that I started to think about (on paper only, no code written yet, but I believe that a "hungry" algorithm - getting as many points as possible at each stage, a bit of backtrack - will lead to solution), so why I started thinking about: looking to Roger Phillips' solution for 13, I said "hey, this solution is wrong, the bright green circle can not pass through 3 points which are collinear" (in Ernst's notation, that is K1, L2 M3), then I started counting circles, they are only 18, so one is missing, and when you enlarge the picture you see that indeed, there is a normal-green circle, and a yellow circle close to it, that makes it appear bright green. This divagation made me look deeper into the a13 case, I am almost certain* you can not make it with 18. I may be able to prove it, given some more time...


Edit: I think you can propose the problem for "ponder this", ask for a(15), ha? Even if it is debated here, and you can give the link, the submitters still would have to think about, write code, etc. You may connect with "extending oeis" sequence, hehe, I hope they will accept it, and publish it for October. Now I am a bit selfish because I will be in Germany in October, visiting a customer for 2-3 weeks, so no time for solving and submission, whatever the problem will be, and I don't want to lose another problem which could be nicer...

------------------
* this means feeling, or guts, not proof yet

[ewmayer]

Originally Posted by LaurV

I think* a13=19 is the right, and "almost" I can prove the 18 circles are not enough. What intrigued me, that I started to think about (on paper only, no code written yet, but I believe that a "hungry" algorithm - getting as many points as possible at each stage, a bit of backtrack - will lead to solution)

My 5x5 solution was basically a greedy approach with some backtracking as soon as I realized that too much symmetry wrecks solvability. Just for getting practice with the Mac OS X standard-install Grapher app, I spent a few hours hand-solving for the circles and plotted it up:

[ewmayer]

Re. the 5x5, I briefly thought that no circle can share the same center [2,2] as that of the 5x5 grid, but as this second solution shows, that is not so (here I now list all points hit by each circle first, then in [] the count and list of new points hit by the circle in question):

[1] BCFIKNQR [8: BCFIKNQR]
[2] GHKNPSVW [6: GHPSVW]
[3] HILOQTWX [4: LOTX]
[4] AEUY [4: AEUY]
[5] DJM [3: DJM]

For my plot of solution #1 I computed all the circle parameters by hand, but this time (really just for the nontrivial circle [5]) I saved some tedium by first working out the derivation of the params for an arbitrary circle with center at [x0,y0] and radius r, (x-x0)^2 + (y-y0)^2 = r^2, passing through 3 noncollinear points [x1,y1], [x2,y2], [x3,y3]. Here x0,y0,r are the 3 desired params, solving for them gives:

	(x3^2 + y3^2) - (x1^2 + y1^2) - ((x3^2 + y3^2) - (x2^2 + y2^2)) * (y3-y1)/(y3-y2)
1. x0 = --------------------------------------------------------------------------------- ,
			2*((x3-x1) - (y3-y1)*(x3-x2)/(y3-y2))

2. y0 = ((x3^2 + y3^2) - (x1^2 + y1^2) - 2*(x3-x1)*x0) / (2*(y3-y1)) ,

3. r^2 = (x1-x0)^2 + (y1-y0)^2 .

The noncollinearity requirement for solvability appears in the form of the requirement of a nonvanishing denominator in the expression for x0.

The 5-circle solution differs from my previous one (nontrivially, i.e. not just via reflection/rotation), but the pattern of 'new points hit' with each added circle is the same: 8,6,4,4,3. Here in pretty-picture form:

[R. Gerbicz]

The sequence is live: http://oeis.org/A262355