Competition problem — Combinatorics

Library / /333 of 520

Combinatorics Difficulty 5.8 AIME, harder Prove it

Consider 21 points on a circle. Show that at least 100 pairs of these points define a central angle less than or equal to $120^{\circ}$ .

Solution

Let's find the right triangle-free graph: we connect two points if the central angle they define is strictly greater than $120^{\circ}$ . Three such points are then never connected pairwise, so the graph is triangle-free. The number of edges is then less than or equal to $21^{2} / 4$ , which is 110. In the complementary graph, there are therefore $\binom{21}{2}-110=100$ edges, which concludes.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.