All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Points On A Circle (Posted on 2004-08-14)
I placed six points on the circumference of a circle such that the distance between any two of the points is an integer. What is the smallest such circle I could use?

What if each distance must be unique?

 No Solution Yet Submitted by ThoughtProvoker Rating: 4.4286 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Impossibly Hard... | Comment 14 of 17 |

This problem hasn't been commented on for a while, but I've given this one a lot of thought from time to time.  My hope is that someone can take some of my ideas and arrive at a solution (for the distinct case).

First of all, the user sundberg was my officemate during an internship I had this summer - he and I worked on this puzzle constantly, and his comments represent what we were able to find (solutions with four points and with five points).  Unless if there was a flaw in our reasoning or our code, it seems that the smallest radius for six points is >1000.

Our idea was to fix a constant N and to find all triangles with maximum side less than N.  For each of these triangles, we can compute a circumradius by combining the formulas

area = abc/(4R)

and

area = sqrt(s(s-a)(s-b)(s-c))

where s is the semiperimeter (a+b+c)/2 and R is the circumradius.  These radii had to be computed exactly (we made an IrrationalNumber class).

We then made a hash map mapping radii to lists of triangles with that circumradius.  We then checked each circumradius up to N/2.  This check was performed by a number of heuristics.  The best algorithm we could come up was roughly something like:

IF (list.size<20) INVALID
MAKE MAP side_to_tris with (side_length -> {triangles list}) mappings
FOR EACH (side_length, triangles_list) in side_to_tris
IF (triangles_list.size<4)  REMOVE mapping, remove all triangles in triangles_list from side_to_tris
REPEAT UNTIL NO MORE TRIANGLES CAN BE REMOVED
BRUTE FORCE CHECK LEFTOVER

The brute force check used Ptolemy's Theorem, which states that in any cyclic quadrilateral ABCD, we have:

The 20 was used since there must be C(6,3)=20 distinct triangles, and 4 was used since for any side length, there must be at least 4 triangles with that side length.

We incrementally increased N, keeping track of which radii we knew we didn't need to test.

I honestly doubt that ThoughtProvoker had a solution in mind for the distinct case.  But it sure would be neat to find it.

 Posted by David Shin on 2004-09-26 01:36:10

 Search: Search body:
Forums (0)