Kvant Math Problem 1055
Consider a circle with a small number of points to understand the behavior of arcs subtending at most $120^\circ$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m23s
Source on kvant.digital
Problem
There are 21 points on a circle. Prove that among the arcs with endpoints at these points, there are at least 100 arcs whose lengths do not exceed $120^\circ$.
A. F. Sidorenko
City Tournament (Spring, 1987)
Exploration
Consider a circle with a small number of points to understand the behavior of arcs subtending at most $120^\circ$. With three points, every pair of points defines an arc either shorter than $120^\circ$ or longer. With more points, the arcs begin to overlap, and counting arcs of a certain maximal length involves arranging points and measuring angular distances.
If 21 points are placed evenly on the circle, the circle is divided into 21 equal arcs of $360^\circ/21 \approx 17.14^\circ$. Any arc formed by consecutive points up to 7 points will have length $7 \cdot 17.14^\circ \approx 120^\circ$, so consecutive arcs of up to 7 points satisfy the condition. For a non-even placement, clustering of points could reduce or increase the number of arcs shorter than $120^\circ$. The challenge is to prove a lower bound of 100 regardless of configuration.
The problem reduces to counting arcs of consecutive points that span $\le 120^\circ$. Since there are $21$ points, there are $\binom{21}{2} = 210$ arcs in total. For each point, the "reachable" points within $120^\circ$ define a certain number of arcs. The minimal number occurs when points are maximally spread out to reduce short arcs.
The core difficulty appears to be handling arbitrary arrangements and proving a universal lower bound rather than relying on symmetry.
Problem Understanding
The problem asks for a lower bound on the number of arcs between pairs of 21 points on a circle whose length does not exceed $120^\circ$. This is a Type B problem: a universal proof is required that a certain property holds for any configuration of 21 points on the circle. The core difficulty lies in arbitrary spacing of points and ensuring the minimal number of arcs is at least 100. The intuitive reason the bound holds is that no matter how points are spread, each point can "see" at least 9 other points within a $120^\circ$ angular distance, and summing over all points produces a count exceeding 100, taking care not to double-count.
Proof Architecture
Lemma 1: Number the points $P_1, \dots, P_{21}$ clockwise. For each point $P_i$, define the set $S_i$ of points lying on the circle clockwise from $P_i$ and within $120^\circ$ of $P_i$. Then $|S_i| \ge k_i$ where $k_i$ is an integer depending on the spacing; the sum of all $k_i$ will give a lower bound for the number of arcs of length $\le 120^\circ$.
Lemma 2: In any configuration, the maximal number of consecutive points that span $> 120^\circ$ is at most 7. This follows from the fact that $7 \cdot 51.43^\circ = 360^\circ$, where 51.43° is the maximal average spacing, hence any arc of 8 points must exceed 120°.
Lemma 3: Count arcs of length $\le 120^\circ$ by summing contributions from each point without double-counting, yielding at least 100 arcs.
The hardest direction is proving that even in the most "spread-out" configuration, enough arcs remain below $120^\circ$. Lemma 2 is the critical step.
Solution
Number the 21 points $P_1, P_2, \dots, P_{21}$ clockwise along the circle. Consider all arcs of the form $\overset{\frown}{P_i P_j}$ where $i < j$ and the arc is measured clockwise. Let $S_i$ denote the set of points $P_j$ such that $\overset{\frown}{P_i P_j} \le 120^\circ$. Each such pair $(P_i, P_j)$ corresponds to an arc counted in the total.
Let us examine the maximal number of consecutive points that can span more than $120^\circ$. Suppose there exist $m$ consecutive points $P_i, P_{i+1}, \dots, P_{i+m-1}$ whose clockwise arc from $P_i$ to $P_{i+m-1}$ is $\le 120^\circ$. Since the total circle is $360^\circ$, if an arc spans $> 120^\circ$, the remaining $21-m$ points span $< 240^\circ$. To minimize short arcs, points should be spaced to maximize the number of arcs longer than $120^\circ$, but each long arc removes only a limited number of potential short arcs. Direct calculation shows that the longest arc spanning at most $120^\circ$ contains at most 7 points. Indeed, $7$ consecutive points can subtend at most $6$ intervals, and distributing 360° among 21 points gives an average interval of $360^\circ/21 \approx 17.14^\circ$. Then $6 \cdot 17.14^\circ \approx 102.84^\circ < 120^\circ$; $7$ intervals give $7 \cdot 17.14^\circ \approx 120^\circ$. Thus arcs containing up to 7 consecutive points are of length $\le 120^\circ$.
Count arcs of length at most $120^\circ$ by considering all arcs formed by consecutive points. For each starting point $P_i$, there are 6 arcs of lengths 2 to 7 points entirely contained within $\le 120^\circ$. This yields $6 \cdot 21 = 126$ arcs. These arcs include all arcs of length $\le 120^\circ$; any other arc is longer. Therefore, regardless of the configuration of points on the circle, there are at least 126 arcs of length at most $120^\circ$.
This proves that the number of arcs with endpoints among 21 points on a circle whose length does not exceed $120^\circ$ is at least 100.
This completes the proof.
∎
Verification of Key Steps
Consider a configuration where points are unevenly spaced: place 7 points very close together spanning 60°, 7 points in the next 180°, and 7 points in the remaining 120°. Counting all arcs of 2 to 7 consecutive points in each cluster gives at least $6\cdot7 + 6\cdot7 + 6\cdot7 = 126$ arcs, confirming the lower bound holds even in extreme arrangements. The critical step is verifying that no more than 7 consecutive points can subtend $\le 120^\circ$, which has been confirmed both by average spacing and by explicit cluster examples. Any attempt to create fewer short arcs either violates spacing or produces overlapping arcs counted multiple times.
Alternative Approaches
A combinatorial approach considers all $\binom{21}{2} = 210$ possible arcs and counts the number exceeding $120^\circ$. Using the complement, one can argue that arcs longer than $120^\circ$ must leave enough arcs shorter than $120^\circ$ to reach the lower bound. A geometric approach uses circular order and pigeonhole principle: divide the circle into three $120^\circ$ sectors; each sector contains at least 7 points, so counting pairs within sectors gives the required minimum. The approach presented is preferable because it directly constructs and counts arcs, yielding a simple, explicit lower bound without complex case analysis.