20150917, 08:56  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5,743 Posts 
Circles Puzzle
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? 
20150917, 12:33  #2 
"William"
May 2003
New Haven
2^{2}·3^{2}·5·13 Posts 
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 noncolinear points determine a circle, there are many ways to get the final nine points.
Last fiddled with by wblipp on 20150917 at 12:34 
20150917, 12:52  #3 
Jun 2003
17·281 Posts 
Don't these two circles have common points?

20150917, 19:24  #4 
"Robert Gerbicz"
Oct 2005
Hungary
2^{3}×3×59 Posts 
Very nice puzzle. My c code found the optimal solution for n=6,7,8.

20150917, 19:25  #5 
"Robert Gerbicz"
Oct 2005
Hungary
2^{3}×3×59 Posts 
Since 8 circles is enough for n=8 these solutions are also optimal for n=7.

20150917, 21:52  #6 
"Robert Gerbicz"
Oct 2005
Hungary
2^{3}×3×59 Posts 
For n=9 and n=10 the optimal solution is 11 circles, so it is enough to give a solution for n=10.

20150918, 01:53  #7 
Romulan Interpreter
Jun 2011
Thailand
3·13·229 Posts 
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.. )

20150918, 02:48  #8 
Jun 2003
17×281 Posts 

20150918, 05:48  #9 
∂^{2}ω=0
Sep 2002
República de California
2^{5}×307 Posts 
I avoided looking at any but the OP while working out a 5circle 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 1. Circle centered at [1.5,2.5] (i.e. at the crossing of the GM and HL diagonals), passing through BCFIKNQR (8 points, 17 remaining); 2. Circle centered at [3.5,2.5] and passing through (I list only previouslyunhit 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 GM diagonal and passing through AOW (3 points; 0 remaining). More interestingly would be to: [1] Prove that 5 circles is the minimum count for the 5x5 case; [2] Prove that a 5circle coverings of the 5x5 case cannot be symmetric under 90degree 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. Last fiddled with by ewmayer on 20150920 at 07:36 Reason: Flip x0,y0 in step [3] of my solution. 
20150918, 14:42  #10  
"Robert Gerbicz"
Oct 2005
Hungary
10110001000_{2} Posts 
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)>(4y,x). ( if the grid is [0,4]X[0,4] ). 

20150918, 16:55  #11 
"William"
May 2003
New Haven
100100100100_{2} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Inscribed Circles  a1call  Puzzles  7  20170626 13:48 
calculating with circles  diep  Homework Help  9  20140712 12:14 
a puzzle  bcp19  Puzzles  18  20120302 04:11 
4 4s puzzle  henryzz  Puzzles  4  20070923 07:31 
Circles part 2  mfgoode  Puzzles  10  20041227 15:17 