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?
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:
AB*CD+AD*BC = AC*BD.
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.
Impossibly Hard...
