Circles Puzzle

[henryzz]

I have found a very nice explanation of a puzzle http://datagenetics.com/blog/june12015/index.html
He solves it there but I was wondering is there a better way of solving it. His solution involved 5 deep nested loops.

Can anyone find a solution for larger grids than 5x5? How many circles are needed for 6x6, 7x7 etc?
Can anyone come up with a more extendible solution than his which has a quite bad runtime order?

[wblipp]

You can get the 8 midside points of a 4x4 grid with one circle. That grid must include a corner point. Do it again with a 4x4 grid in the diagonally opposite corner. That gets 16 points with two circles, leaving nine points to cover with three circles. Since any three non-co-linear points determine a circle, there are many ways to get the final nine points.

[axn]

Originally Posted by wblipp

You can get the 8 midside points of a 4x4 grid with one circle. That grid must include a corner point. Do it again with a 4x4 grid in the diagonally opposite corner. That gets 16 points with two circles, leaving nine points to cover with three circles

Don't these two circles have common points?

[R. Gerbicz]

Originally Posted by henryzz

Can anyone find a solution for larger grids than 5x5? How many circles are needed for 6x6, 7x7 etc?
Can anyone come up with a more extendible solution than his which has a quite bad runtime order?

Very nice puzzle. My c code found the optimal solution for n=6,7,8.

[R. Gerbicz]

Since 8 circles is enough for n=8 these solutions are also optimal for n=7.

[R. Gerbicz]

For n=9 and n=10 the optimal solution is 11 circles, so it is enough to give a solution for n=10.

[LaurV]

That is becoming interesting... How many integer point can you get on a circle of big/whatever/almost_infinite (grrr!) radius? Or say, rational points on a circle of radius 1. Can this be used to factor integers? (thinking to something equivalent to elliptic curves, haha, now I will attract Bob's wrath, for sure.. )

[axn]

Originally Posted by R. Gerbicz

Very nice puzzle. My c code found the optimal solution for n=6,7,8.

For 6x6, there is a very pretty solution with just concentric circles.

[ewmayer]

I avoided looking at any but the OP while working out a 5-circle covering for the 5x5 case: Let's alphabetize the points like so:

A  B  C  D  E

F  G  H  I  J

K  L  M  N  O

P  Q  R  S  T

U  V  W  X  Y

...and further define a Cartesian coordinate system with origin at U; A at [0,4], Y at [4,0], etc. One obvious solution is as follows:

1. Circle centered at [1.5,2.5] (i.e. at the crossing of the G-M and H-L diagonals), passing through BCFIKNQR (8 points, 17 remaining);
2. Circle centered at [3.5,2.5] and passing through (I list only previously-unhit points) DEHMST (6 points; 11 remaining);
3. Circle centered at [1.5,0.5] and passing through LPUX (4 points; 7 remaining);
4. Circle centered at [2.5,1.5] and passing through GJVY (4 points; 3 remaining);
5. Circle centered at the appropriate spot on the G-M diagonal and passing through AOW (3 points; 0 remaining).

And now I see that wblipp has posted a different (and inductively more elegant) solution for the 5x5 case. (Edit: whoops! See axn's note in post #3.)

More interestingly would be to:

[1] Prove that 5 circles is the minimum count for the 5x5 case;
[2] Prove that a 5-circle coverings of the 5x5 case cannot be symmetric under 90-degree rotations.

From the OP link:

I enjoyed this puzzle. It's the kind of puzzle that it's fun to write code to solve. I don't think it would have been as fun to solve with a piece of paper as it's hard to draw perfect circles.

Not in one's mind, it's not. I simply used the picture of the grid to aid in keeping track which points had already been hit.

[R. Gerbicz]

Originally Posted by axn

For 6x6, there is a very pretty solution with just concentric circles.

OK, my current code not searched for that very special or symmetric solutions. However some of my posted solutions are also symmetric.

Originally Posted by ewmayer

[1] Prove that 5 circles is the minimum count for the 5x5 case;

For n=5 we need 5 circles. Btw this sequence is not in OEIS (define a(n)=c if the optimal number of circles is c on the nXn grid).

What I have found that on the blog the total number of (optimal) configurations for n=5 is wrong, see for example the first and the 10th solution, these are the same after a 90 degree rotation, so (x,y)->(4-y,x). ( if the grid is [0,4]X[0,4] ).

[wblipp]

Originally Posted by axn

Don't these two circles have common points?

NO

A  B  C  D  E

F  G  H  I  J

K  L  M  N  O

P  Q  R  S  T

U  V  W  X  Y

The first circle gets B, C, I, N, R, Q. K, F

The second circle gets H, I, O, T, X, Y, Q, L