There are 3333 points on the circumference of a circle that divide it into 3333 equal parts. These points are numbered consecutively and clockwise as 0,1,2,3,…,320, 1, 2, 3, \dotsc, 32. Some of these points are painted red with the property that no two pairs of red points are the same distance apart (we define the distance of two points on the circumference as the minimum arc length between these points). What is the highest number of points that can be painted red?

=================

I think I found the upper bound, but I’m having trouble proving that it is not possible with 88 points.

– Rigo

2 days ago

Hmm, I thought the “obvious” upper bound was 66, since with 77 points, there are 7⋅67\cdot 6 differences, which is greater than 3232. Did you find an example with 77?

– Thomas Andrews

2 days ago

1

Effectively, the highest number of points is 5 because let’s say we paint one point red and then we paint another such that their distance is xx. Then we paint another one such that the distance between the second point and this new one is yy. This way we won’t be able to use x+yx+y or 33−(x+y)33-(x+y) (I’m going to assume the distance between two consecutive points is 1) Repeat this with another point and distance zz, we won’t be able to use 15=5∗315=5*3 distances (which is the number of distances with 66 points)

– Rigo

2 days ago

1

If you paint 0, 1, 3 and 6, the distance between 0 and 3 is the same distance between 3 and 6.

– Rigo

2 days ago

1

It’s not clear why we can’t get 1515 distinct distances, @Rigo. It might be hard, but there are 1616 possible non-zero values for the distances.

– Thomas Andrews

2 days ago

=================

=================