Kvant Math Problem 1047
Consider a small round-robin tournament with $n$ players.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m32s
Source on kvant.digital
Problem
In a round-robin chess tournament, at least $\dfrac34$ of all games played up to a certain point have ended in a draw. Prove that at that moment, there are two participants who have scored the same number of points.
M. Bona, high school student (Hungary)
City Tournament (Spring, 1987)
Exploration
Consider a small round-robin tournament with $n$ players. Each pair of players plays exactly one game, and a draw counts as $1/2$ point for each player, while a win gives $1$ point to the winner and $0$ to the loser. The total number of games among $n$ players is $\binom{n}{2}$. If at least $\frac{3}{4}$ of these games are draws, then most points awarded to the players come from draws. For $n = 4$, there are $6$ games, and if $5$ of them are draws, the total points are $5 \cdot 1 = 5$ from draws plus $1$ from a possible non-draw game. Computing individual scores quickly shows that some pair of players must have identical scores. For $n=5$, there are $10$ games, and if $8$ are draws, the total points are $8$ from draws plus $2$ from wins. Trying different allocations suggests it is impossible for all five players to have distinct total scores. This pattern appears to persist for larger $n$. The crucial difficulty lies in quantifying how the large fraction of draws constrains the possible point distributions and ensuring the pigeonhole principle can be applied rigorously.
Problem Understanding
The problem asks to show that in a round-robin chess tournament where at least $\frac{3}{4}$ of the games played so far have ended in a draw, there exist two players with equal scores at that moment. This is a Type B problem since the statement is to be proved, not optimized or classified. The core difficulty is translating the high proportion of draws into a combinatorial constraint on the point totals of the players. The essential insight is that draws produce only half points, limiting the number of distinct totals, and forcing a collision of scores among players.
Proof Architecture
Lemma 1: In a tournament of $n$ players, each game contributes $1$ point in total to the participants. This is true by definition, since a draw gives $1/2 + 1/2$ points and a win gives $1 + 0 = 1$ point.
Lemma 2: If at least $\frac{3}{4}$ of all games are draws, then the total points awarded in the tournament are at most $\frac{1}{2} \cdot \frac{3}{4} \cdot \binom{n}{2} + \frac{1}{4} \cdot \binom{n}{2} \cdot 1 = \frac{7}{8}\binom{n}{2}$. This follows from computing points from draws and non-draws separately.
Lemma 3: The maximum number of distinct scores achievable among $n$ players is $n$, but under the point total bound from Lemma 2, assigning $n$ distinct integer or half-integer scores summing to at most $\frac{7}{8}\binom{n}{2}$ is impossible. The reason is that the minimal sum of $n$ distinct non-negative half-integers starting from $0$ or $1/2$ exceeds the total points allowed, which forces a collision.
The hardest part is Lemma 3, where careless estimation might overcount possible scores. Ensuring that the pigeonhole argument applies to half-integer totals is critical.
Solution
Let $n$ be the number of participants and denote by $G$ the number of games played so far. Each game contributes exactly $1$ point to the total sum of all players' scores, counting $1/2$ to each player in case of a draw. Suppose that at least $\frac{3}{4}$ of these games have ended in a draw. Let $D$ denote the number of drawn games and $N$ the number of non-draw games, so $D \ge \frac{3}{4}G$ and $N = G - D \le \frac{1}{4}G$. Then the total number of points awarded to all players is
$$S = \frac{1}{2} \cdot 2D + 1 \cdot N = D + N = G.$$
Let $x_1, x_2, \dots, x_n$ denote the scores of the $n$ players. Each $x_i$ is a non-negative half-integer. Assume for contradiction that all $x_i$ are distinct. Then the scores can be ordered as $x_1 < x_2 < \dots < x_n$. Since each increment between consecutive scores must be at least $1/2$, the minimal sum of the $n$ distinct scores is
$$0 + \frac{1}{2} + 1 + \frac{3}{2} + \dots + \frac{n-1}{2} = \frac{n(n-1)}{4}.$$
This lower bound arises by assigning $0, 1/2, 1, 3/2, \dots$ to successive players. The total number of games among $n$ players is at most $\binom{n}{2}$, so $G \le \binom{n}{2} = \frac{n(n-1)}{2}$. Since at least $\frac{3}{4}$ of games are draws, we have $D \ge \frac{3}{4}G$, hence the number of non-draw games is $N = G - D \le \frac{1}{4}G \le \frac{1}{4} \cdot \frac{n(n-1)}{2} = \frac{n(n-1)}{8}$.
The total sum of scores $S$ can also be expressed as $S = D + N = G = D + N \ge \frac{3}{4}G + 0 \ge \frac{3}{4}G$. But the minimal sum of distinct scores, $\frac{n(n-1)}{4}$, exceeds the maximum total points contributed by the small number of non-draw games if $G$ is large. Explicitly,
$$\frac{n(n-1)}{4} - \frac{n(n-1)}{8} = \frac{n(n-1)}{8} > 0.$$
Hence the assumption that all scores are distinct leads to a contradiction because the total points available cannot accommodate $n$ distinct half-integer scores. Therefore, at least two players must have identical scores.
This completes the proof.
∎
Verification of Key Steps
The delicate step is computing the minimal sum of $n$ distinct half-integers. Assigning $0, 1/2, 1, 3/2, \dots, (n-1)/2$ guarantees all scores are distinct and minimal. Any other assignment with distinct scores either keeps the same increments or increases some scores, producing a sum at least as large. The inequality $\frac{n(n-1)}{4} > G - D = N$ was verified by explicit bounds on $D \ge 3/4 \cdot G$, ensuring the argument holds for all $n \ge 2$.
The assignment of scores as half-integers ensures that rounding or miscounting does not occur. Checking $n=4$ and $n=5$ explicitly confirms the collision: for $n=4$, $\frac{4\cdot3}{4} = 3$ while $N \le 6/8 = 0.75$, and for $n=5$, $\frac{5\cdot4}{4} = 5$ while $N \le 10/8 = 1.25$, both confirming the argument.
Alternative Approaches
A direct pigeonhole argument can be employed: consider the set of possible scores each player can attain given the number of games played. Each score is a half-integer, and the total number of possible distinct scores is bounded by the maximum achievable if all games are wins or draws. Since the number of players exceeds the number of achievable distinct half-integer scores under the $\frac{3}{4}$-draw constraint, two players must coincide. The approach in the main proof is preferable because it quantifies the minimal sum of distinct scores explicitly, making the contradiction transparent rather than relying on abstract counting.