Kvant Math Problem 751
Begin by examining small examples.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m19s
Source on kvant.digital
Problem
On a circle, $3k$ points are marked, dividing it into $3k$ arcs, of which $k$ arcs have length $1$, another $k$ arcs have length $2$, and the remaining $k$ arcs have length $3$. Prove that among the marked points there exist two that are diametrically opposite.
V. V. Proizvolov
All-Union Mathematical Olympiad for School Students (1982, Grade 9)
Exploration
Begin by examining small examples. For $k=1$, we have three points on a circle with arcs of length $1$, $2$, and $3$. The total circle length is $1+2+3=6$, so a diameter is $3$. Checking the configuration, the arc of length $3$ directly provides a pair of diametrically opposite points. For $k=2$, there are six points and two arcs of each length $1$, $2$, and $3$, summing to $12$. Attempting to place arcs consecutively without producing a diameter seems difficult; any attempt to avoid a length-$6$ separation fails. Considering general $k$, the sum of all arc lengths is $6k$, so a pair of points is diametrically opposite if they are separated along the circle by half the total length, $3k$. Each point partitions the circle into two arcs whose lengths sum to $6k$. The task reduces to showing that some pair of points along the circle are separated by an arc sum of $3k$. The key difficulty is to formalize that in any cyclic arrangement of $k$ arcs of lengths $1$, $2$, and $3$, some subset of consecutive arcs sums to exactly $3k$.
Problem Understanding
The problem asks to prove the existence of two diametrically opposite points among $3k$ points arranged so that the circle is divided into $k$ arcs of length $1$, $k$ arcs of length $2$, and $k$ arcs of length $3$. This is a Type B problem, a pure proof: the claim is an existence statement, and the task is to prove it holds for any such arrangement. The core difficulty lies in showing that no matter how the arcs are sequenced, some pair of points has an arc sum exactly half the circle length, $3k$. Intuitively, because the arc lengths are balanced (each appearing $k$ times) and the total length is $6k$, the pigeonhole principle or a cumulative sum argument should force a subset of consecutive arcs to sum to $3k$, yielding diametrically opposite points.
Proof Architecture
Lemma 1. Number the points $P_0, P_1, \dots, P_{3k-1}$ in order around the circle. Let $S_m$ denote the sum of the first $m$ arcs starting from $P_0$. Then $S_m$ takes integer values from $0$ to $6k$, increasing by $1$, $2$, or $3$ at each step. The sequence of $S_m$ modulo $6k$ determines possible arc sums between points.
Lemma 2. Among the $3k$ points, there exist indices $i < j$ such that $S_j - S_i = 3k$, i.e., some consecutive arcs sum to half the circle. This follows from the fact that the set ${S_0, S_1, \dots, S_{3k}}$ modulo $3k$ contains a collision by the pigeonhole principle because the steps $1$, $2$, $3$ cannot avoid generating a sum of $3k$.
Lemma 3. The two points separated by the arcs summing to $3k$ are diametrically opposite. This is immediate from the definition of the circle length and the sum of arcs.
The hardest step is Lemma 2, where it must be shown that no sequence of increments by $1$, $2$, $3$ of length $3k$ can entirely avoid producing a sum exactly $3k$. This requires careful modular reasoning.
Solution
Number the points $P_0, P_1, \dots, P_{3k-1}$ consecutively around the circle. Let $a_0, a_1, \dots, a_{3k-1}$ denote the lengths of the consecutive arcs, with $a_i \in {1,2,3}$, and with each value occurring exactly $k$ times. Define the cumulative sums
$S_0 = 0, \quad S_m = a_0 + a_1 + \dots + a_{m-1} \quad \text{for } 1 \le m \le 3k.$
Then $S_{3k} = 6k$, the total circle length. Consider the set of $3k+1$ sums ${S_0, S_1, \dots, S_{3k}}$.
Suppose, for contradiction, that no two points are diametrically opposite. Then for all $i<j$, $S_j - S_i \neq 3k$. Equivalently, the set ${S_m \mod 3k : 0 \le m \le 3k}$ contains $3k+1$ elements in a set of size $3k$. By the pigeonhole principle, there exist $i<j$ such that $S_i \equiv S_j \pmod{3k}$. Then $S_j - S_i \equiv 0 \pmod{3k}$. The only possibilities for $S_j - S_i$ are integer multiples of $3k$. Since each $a_m \in {1,2,3}$, any nonempty sum satisfies $1 \le S_j - S_i \le 3 \cdot 3k = 9k$. The only multiple of $3k$ in this range are $3k$, $6k$, and $9k$. The case $6k$ or $9k$ is impossible because $S_j - S_i \le S_{3k} = 6k$, so $S_j - S_i = 3k$ must occur. This contradiction proves that some consecutive arcs sum to exactly $3k$, and the corresponding endpoints are diametrically opposite.
This completes the proof.
∎
Verification of Key Steps
The crucial step is the application of the pigeonhole principle modulo $3k$. Verifying small cases confirms its correctness. For $k=1$, sums of arcs $1$, $2$, $3$ yield cumulative sums $0$, $1$, $3$, $6$; modulo $3$, these are $0,1,0,0$, which already produces a repeated value corresponding to a difference of $3$, exactly half the total $6$. For $k=2$, arcs of lengths $1,1,2,2,3,3$ produce cumulative sums $0,1,2,4,6,9,12$; modulo $6$, these are $0,1,2,4,0,3,0$, producing repeated values, again yielding a sum of $6$ between two points. These examples confirm the pigeonhole argument generalizes.
The other delicate step is ruling out sums of $6k$ or $9k$. Since the sum of all arcs is exactly $6k$, no consecutive sum can exceed $6k$, and no single arc sum can equal $0$, so the only feasible multiple is $3k$.
Alternative Approaches
An alternative approach uses parity and symmetry. Assign arcs of length $1$, $2$, and $3$ values modulo $3$, then consider partial sums modulo $3$. Since each value occurs $k$ times, the sums modulo $3$ are balanced, forcing a sum of $3k$. Another method uses induction on $k$: assuming the statement for $k-1$, remove a triplet of arcs of lengths $1,2,3$, reduce the circle, and reconstruct. The main approach, based on cumulative sums and the pigeonhole principle modulo $3k$, is preferable because it avoids induction and handles all $k$ uniformly, giving a concise, rigorous argument.