21 points on circumference of a circle must have at least 100 pairs separated by 120+ degrees.

Question

Prove that at least 100 of the arcs determined by the pairs of these points subtend an angle not exceeding 120 degrees at the center. How do I prove this? Induction? Help please. Thanks.

Answer 1

Since the angle subtended by any 2 adjacent points is $360^\circ/21$, we need to have a 7 point gap to subtent an angle of $360^\circ/21 * 7 = 120^\circ$.

Hence, 8 adjacent points subtend $120^\circ$, and any smaller number of points will subtend $<120^\circ$. So, we can pick $8, 7, \ldots 2$ adjacent points and they will all subtend the angle we want.

The number of $n$-adjacent points that exist on a circle will be $p - n + 1$, where $p$ is the total number of points.

Computing $S = \sum_{i=2}^8 p - i + 1 = \sum_{i=2}^8 21 - i + 1 = 97$ (if one does the math)

I'm not sure what I'm missing - however, I do believe that if we are to take the smaller angle when the arc angle crosses $180^\circ$ (example, if I cut out a $300^\circ$ arc, do we take the arc angle to be $60^\circ$? In that case, the complement of all arcs that have arc angles greater than $360^\circ - 120^\circ = 140^\circ$ will also need to be computed. This will definitely push the number of arcs to over a hundered

Answer 2

Form a graph with 21 vertices corresponding to the points and edges between pairs of points more than 120 degrees apart.

This graph is triangle-free.

The number of edges in a triangle-free graph on 21 vertices is (uniquely) maximized for the bipartite graph on 10 + 11 vertices which has 110 edges. Therefore, there are at least ${21 \choose 2} - 110 = 210 - 110 = 100$ pairs of vertices not joined by an edge. Those pairs correspond to pairs of points at most 120 degrees apart.

This also explains what the maximal arrangements of points look like. All of them can be formed by taking two disjoint closed 120 degree arcs on the circle, and placing $10$ and $11$ points respectively inside the two open intervals that are the complement of those arcs.