mersenneforum.org Circles Puzzle
 Register FAQ Search Today's Posts Mark Forums Read

 2015-09-17, 08:56 #1 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 16A216 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?
 2015-09-17, 12:33 #2 wblipp     "William" May 2003 New Haven 23·5·59 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 non-co-linear points determine a circle, there are many ways to get the final nine points. Last fiddled with by wblipp on 2015-09-17 at 12:34
2015-09-17, 12:52   #3
axn

Jun 2003

2·32·269 Posts

Quote:
 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?

2015-09-17, 19:24   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101100101002 Posts

Quote:
 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.
Attached Files
 n=6;6 circles.pdf (879.2 KB, 160 views) n=7;8 circles.pdf (820.0 KB, 93 views)

2015-09-17, 19:25   #5
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

22×3×7×17 Posts

Since 8 circles is enough for n=8 these solutions are also optimal for n=7.
Attached Files
 n=8; 8 circles.pdf (820.1 KB, 83 views)

2015-09-17, 21:52   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

142810 Posts

For n=9 and n=10 the optimal solution is 11 circles, so it is enough to give a solution for n=10.
Attached Files
 n=10;11 circles.pdf (820.4 KB, 92 views)

 2015-09-18, 01:53 #7 LaurV Romulan Interpreter     Jun 2011 Thailand 913610 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.. )
2015-09-18, 02:48   #8
axn

Jun 2003

113528 Posts

Quote:
 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.

 2015-09-18, 05:48 #9 ewmayer ∂2ω=0     Sep 2002 República de California 22×3×5×193 Posts 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 ...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. Last fiddled with by ewmayer on 2015-09-20 at 07:36 Reason: Flip x0,y0 in step [3] of my solution.
2015-09-18, 14:42   #10
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

59416 Posts

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

2015-09-18, 16:55   #11
wblipp

"William"
May 2003
New Haven

23·5·59 Posts

Quote:
 Originally Posted by axn Don't these two circles have common points?
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
The first circle gets B, C, I, N, R, Q. K, F

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

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Puzzles 7 2017-06-26 13:48 diep Homework Help 9 2014-07-12 12:14 bcp19 Puzzles 18 2012-03-02 04:11 henryzz Puzzles 4 2007-09-23 07:31 mfgoode Puzzles 10 2004-12-27 15:17

All times are UTC. The time now is 10:54.

Sun Jan 17 10:54:24 UTC 2021 up 45 days, 7:05, 0 users, load averages: 0.85, 1.23, 1.37