Circles Puzzle
 

I have found a very nice explanation of a puzzle [url]http://datagenetics.com/blog/june12015/index.html[/url]
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?

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.

[QUOTE=wblipp;410614]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[/QUOTE]
Don't these two circles have common points?

[QUOTE=henryzz;410600]
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?[/QUOTE]

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

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

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

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? :razz: (thinking to something equivalent to elliptic curves, haha, now I will attract Bob's wrath, for sure.. :bob:)

[QUOTE=R. Gerbicz;410675]Very nice puzzle. My c code found the optimal solution for n=6,7,8.[/QUOTE]

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

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:
[code]
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
[/code]
...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:
[spoiler]
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).[/spoiler]

[strike]And now I see that wblipp has posted a different (and inductively more elegant) solution for the 5x5 case.[/strike] (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]
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.
[/i]
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.

[QUOTE=axn;410723]For 6x6, there is a very pretty solution with just concentric circles.[/QUOTE]
OK, my current code not searched for that very special or symmetric solutions. However some of my posted solutions are also symmetric.
[QUOTE=ewmayer;410748]
[1] Prove that 5 circles is the minimum count for the 5x5 case;
[/QUOTE]

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

[QUOTE=axn;410615]Don't these two circles have common points?[/QUOTE]

NO

[code]
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[/code]

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

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