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.