5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is S equal to? I don't get 2nd part below the summation. Can you explain? $\endgroup$ – nyorkr23 Apr 28 '16 at 17:24
  • $\begingroup$ The points do not have to be equally spaced or located at some vertices of a regular 21-gon. $\endgroup$ – zyx Apr 29 '16 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.