mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2015-09-17, 08:56   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22·1,433 Posts
Default 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?
henryzz is offline   Reply With Quote
Old 2015-09-17, 12:33   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

234010 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2015-09-17, 12:52   #3
axn
 
axn's Avatar
 
Jun 2003

5·23·41 Posts
Default

Quote:
Originally Posted by wblipp View Post
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?
axn is online now   Reply With Quote
Old 2015-09-17, 19:24   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×5×47 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
File Type: pdf n=6;6 circles.pdf (879.2 KB, 149 views)
File Type: pdf n=7;8 circles.pdf (820.0 KB, 79 views)
R. Gerbicz is offline   Reply With Quote
Old 2015-09-17, 19:25   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×5×47 Posts
Default

Since 8 circles is enough for n=8 these solutions are also optimal for n=7.
Attached Files
File Type: pdf n=8; 8 circles.pdf (820.1 KB, 70 views)
R. Gerbicz is offline   Reply With Quote
Old 2015-09-17, 21:52   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·3·5·47 Posts
Default

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
File Type: pdf n=10;11 circles.pdf (820.4 KB, 78 views)
R. Gerbicz is offline   Reply With Quote
Old 2015-09-18, 01:53   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

886810 Posts
Default

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.. )
LaurV is offline   Reply With Quote
Old 2015-09-18, 02:48   #8
axn
 
axn's Avatar
 
Jun 2003

5×23×41 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
axn is online now   Reply With Quote
Old 2015-09-18, 05:48   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

263F16 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2015-09-18, 14:42   #10
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

141010 Posts
Default

Quote:
Originally Posted by axn View Post
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 View Post
[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] ).
R. Gerbicz is offline   Reply With Quote
Old 2015-09-18, 16:55   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

234010 Posts
Default

Quote:
Originally Posted by axn View Post
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
wblipp is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 16:30.

Sun Oct 25 16:30:06 UTC 2020 up 45 days, 13:41, 1 user, load averages: 1.90, 1.94, 1.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.