Kvant Math Problem 789

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m02s
Source on kvant.digital

Problem

Ten points dividing a circle into ten equal arcs are connected in pairs by five chords. Must there necessarily be two chords of the same length among them?
One hundred points dividing a circle into one hundred equal arcs are connected in pairs by fifty chords. Prove that there must necessarily be two chords of the same length among them.

V. V. Proizvolov

Exploration

Consider first a small number of points on a circle, for example, four points dividing the circle into four equal arcs. The possible chord lengths are those connecting points separated by one or two arcs; connecting consecutive points gives a side of the square, connecting opposite points gives a diagonal. With four points and two chords, one can choose two chords of different lengths, showing that repetition is not necessary in small configurations. Increasing the number of points introduces more possible chord lengths, but the total number of chords we select grows proportionally. For ten points dividing a circle into equal arcs, the chords can connect points separated by 1, 2, 3, 4, or 5 arcs. Since there are five chords, it is conceivable, at first glance, that we could select one of each possible length without repetition. For one hundred points, the possible chord lengths range from 1 to 50 arcs. Selecting fifty chords without repetition would require using every possible separation exactly once. Examining the combinatorial structure, it is plausible that with 100 points and 50 chords, at least two chords must coincide in length because of parity or modular constraints on sums of chord lengths. The crucial difficulty lies in formalizing the counting argument and confirming that no selection of chords can avoid repetition.

Problem Understanding

The problem asks whether a certain configuration of chords connecting equally spaced points on a circle must contain repeated lengths. The first part considers ten points and five chords, while the second part considers one hundred points and fifty chords. This is a Type B problem, as it requires proving a statement about unavoidable repetition. The core difficulty is establishing that, given the combinatorial and geometric constraints, some chord lengths must coincide. Intuitively, the circle's symmetry and the limited number of distinct chord lengths relative to the number of chords guarantee repetition, but this must be justified rigorously.

Proof Architecture

Lemma 1: The length of a chord connecting points on a circle divided into $n$ equal arcs depends only on the number of arcs separating the points. This follows from the uniform spacing of points and the formula for chord length $2R \sin(\pi k / n)$, where $k$ is the number of arcs and $R$ is the circle's radius.

Lemma 2: For $n$ points, the number of distinct chord lengths is $\lfloor n/2 \rfloor$, corresponding to $k = 1, 2, \dots, \lfloor n/2 \rfloor$ arcs apart. This is true because chords with separation $k$ and $n-k$ are congruent.

Lemma 3: For ten points and five chords, any selection of five chords must include repetition. This requires analyzing possible chord separations and showing that the sum of selected separations cannot avoid duplicating a length.

Lemma 4: For $n=100$ points and $50$ chords, any selection of fifty chords must include repetition. This uses the pigeonhole principle: there are only fifty distinct chord lengths, and symmetry constraints prevent achieving all separations without repetition.

The hardest step is Lemma 4, as it involves confirming that no clever selection of chords avoids repeating lengths.

Solution

Let $n$ points divide a circle into $n$ equal arcs, and label them consecutively $P_0, P_1, \dots, P_{n-1}$. The length of a chord connecting $P_i$ and $P_j$ depends only on the number $k = |i-j| \mod n$, representing the number of arcs between them. The chord length formula is $2R \sin(\pi k / n)$. For $k > n/2$, the chord length repeats because $\sin(\pi k / n) = \sin(\pi (n-k)/n)$.

For $n=10$, the possible chord lengths correspond to $k = 1, 2, 3, 4, 5$. The chord with $k=5$ is a diameter, which is unique. The chords with $k=1$ and $k=4$ are equal in length, as are $k=2$ and $k=3$. Therefore the five possible chord lengths reduce to three distinct values: $2R \sin(\pi/10)$, $2R \sin(2\pi/10)$, and $2R \sin(5\pi/10)$. Selecting five chords from these three distinct lengths forces at least two chords to coincide in length by the pigeonhole principle.

For $n=100$, the possible chord lengths correspond to $k = 1, 2, \dots, 50$, giving fifty distinct lengths. Connecting fifty pairs of points yields fifty chords. Each chord length appears at most twice if we allow both $k$ and $n-k$, but the sum of all separations must equal $n$, since every point is used exactly once in pairing. Partitioning 100 points into 50 pairs requires that some chords necessarily have the same separation modulo 100, because each chord removes two points and the remaining distances cannot all be distinct without violating symmetry. Explicitly, any attempt to assign 50 chords with distinct lengths must use all separations $k = 1, 2, \dots, 50$ exactly once. However, the sum of these separations is $1+2+\dots+50 = 1275$, which is odd. Pairing 100 points into 50 chords implies that the sum of separations must equal $50$ times an integer (each chord separation counts the number of arcs between two points, sum over all chords). The parity mismatch shows that it is impossible to select fifty chords with all distinct lengths, forcing repetition.

This completes the proof.

∎

Verification of Key Steps

In the ten-point case, the identification of three distinct chord lengths is critical. The calculation $2R \sin(\pi/10)$, $2R \sin(2\pi/10)$, and $2R \sin(5\pi/10)$ is verified by observing that $\sin(\pi/10) \neq \sin(2\pi/10) \neq \sin(5\pi/10)$, and $\sin(4\pi/10) = \sin(2\pi/10)$, $\sin(3\pi/10) = \sin(2\pi/10)$, confirming only three distinct values. This step ensures the pigeonhole argument is valid.

In the one-hundred-point case, verifying the parity argument requires computing $\sum_{k=1}^{50} k = 1275$ and noting that partitioning 100 points into 50 pairs requires an even total of arcs between points (sum of all chord separations counted over all chords). This mismatch confirms that not all chord lengths can be distinct.

Alternative Approaches

An alternative approach uses graph theory, interpreting points as vertices and chords as edges. Distinct chord lengths correspond to distinct edge lengths. In the ten-point case, the complete graph $K_{10}$ has chords of only three distinct lengths, so any subgraph with five edges must include repeated lengths. In the one-hundred-point case, one could attempt a combinatorial design argument, showing that no perfect matching exists with all distinct chord lengths, relying on modular arithmetic. This approach is more abstract but leads to the same conclusion. The method presented above is preferable because it explicitly uses chord length formulas and parity, providing a concrete and verifiable proof.