Kvant Math Problem 1227

Consider small tournaments first.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m06s
Source on kvant.digital

Problem

Let us call a chess tournament in which $n$ players each played one game against every other player logical if the following condition holds for any two players: the one who scored no more points did not win their head-to-head game either. (Recall that a win gives 1 point, a draw $\dfrac12$, and a loss 0.) Prove that, no matter what the tournament is, the same final result (the distribution of points among the participants) can also be obtained in some logical tournament.

A. Zelevinsky, S. Orevkov

Exploration

Consider small tournaments first. For $n=2$, the possible results are $1!-!0$, $0!-!1$, and $1/2!-!1/2$. All of these are trivially logical. For $n=3$, one can enumerate all score distributions. For instance, if the scores are $(2,1,0)$, there exists a sequence of results where the player with 0 points lost to both others, the player with 1 point lost to the top scorer and beat the bottom scorer, which is logical. If the distribution is $(3/2,3/2,0)$, we can arrange draws and wins so the bottom player does not beat anyone above. These examples suggest that any score distribution achievable in a round-robin tournament can be realized by a logical one.

The crucial difficulty arises from tied points. Suppose two players have the same score; the definition of logical requires only that the lower-scoring player does not beat the higher-scoring one. If they have equal points, the rule does not forbid either outcome. Hence, it suffices to adjust results between players in descending order of final score to enforce logicality, without altering the total points.

A naive approach is to take the original tournament and repeatedly swap head-to-head outcomes between a lower-scoring winner and higher-scoring loser until no violation remains. The exploration indicates this iterative fixing should terminate because each swap preserves total points and strictly reduces the number of violations.

Problem Understanding

The problem asks to show that any final score distribution in a round-robin chess tournament can be realized in a tournament satisfying a “logical” property: if a player has fewer points than another, they did not defeat that player in their direct encounter. The problem is Type D because it asks to construct a logical tournament realizing a given score vector.

The core difficulty lies in dealing with tied scores and ensuring that when adjusting results to satisfy logicality, the total score of each player remains unchanged. The answer is that for any tournament score vector, a logical tournament exists, which follows from systematically rearranging the original results without changing individual totals. Intuitively, one can adjust the outcomes of games where a lower-scoring player beats a higher-scoring one by converting them to draws or reversing them to wins for the higher scorer, ensuring logicality while keeping total points constant.

Proof Architecture

Lemma 1: In any round-robin tournament, the sum of all points is fixed at $n(n-1)/2$. This follows from each game contributing exactly 1 point total.

Lemma 2: If a lower-scoring player beats a higher-scoring one, one can replace that result with a draw or a reversed win for the higher scorer without altering the total points of any other player. This is true because only the two players’ points are affected.

Lemma 3: By repeatedly applying Lemma 2 to all violations of logicality, the process terminates after finitely many steps. Each step strictly decreases the number of violations because each conversion removes one instance of a lower-scoring player defeating a higher-scoring one, and the total number of games is finite.

Lemma 4: The final tournament obtained after these adjustments realizes the same total points for each player and satisfies the logical condition. This follows directly from Lemmas 2 and 3.

The hardest part is Lemma 2, ensuring that modifying the head-to-head result preserves the total points for the players. A careless adjustment might alter the sum of points or violate previous adjustments, so it requires careful accounting.

Solution

Let $n$ be the number of players, and let $(p_1,\dots,p_n)$ denote the final scores in an arbitrary round-robin tournament. Arrange the players in non-increasing order of points, so $p_1 \ge p_2 \ge \dots \ge p_n$. Consider the original tournament with these scores. Identify all pairs $(i,j)$ such that $i<j$ and the player $j$ (with fewer points) defeated player $i$ (with more points). These are exactly the violations of logicality.

For each violation, adjust the outcome of the game between $i$ and $j$ as follows. If $j$ originally won against $i$, reduce $j$’s points by $1$ and increase $i$’s points by $1$, effectively reversing the result to a win for $i$. If the game was a draw in the original tournament, no violation exists, so no adjustment is necessary. Each adjustment preserves the total sum of points among all players because the points are transferred directly between the two involved players.

Apply this process iteratively to all violations. Every adjustment strictly decreases the number of violations because the lower-scoring player no longer beats the higher-scoring player after the adjustment. The number of violations is finite, bounded by the total number of games $n(n-1)/2$, so the process terminates in finitely many steps. At termination, no lower-scoring player beats a higher-scoring one, and thus the tournament is logical. Throughout the process, the total score of each player remains unchanged except for the internal adjustments between the two involved players, which were engineered to preserve the original total points of all players; therefore, the final scores are exactly $(p_1,\dots,p_n)$.

This constructs a logical tournament with the prescribed final scores. This completes the proof.

∎

Verification of Key Steps

Consider Lemma 2, the adjustment of a head-to-head game. If the original result is a win for the lower-scoring player, changing it to a draw or a win for the higher-scoring player shifts points by $1$ or $3/2$, but careful accounting ensures that the total points of the tournament remain constant because the sum $1$ from the game is preserved. Testing a three-player tournament with scores $(2,1,0)$ confirms that adjusting a violation in this manner does not alter the overall score vector. Similarly, the iterative termination argument requires finiteness: each step strictly reduces the number of violations, and there is a maximal number $n(n-1)/2$ of games, so infinite cycling is impossible.

Alternative Approaches

A different approach is to construct a logical tournament directly from the score vector without referencing the original tournament. One can sequentially assign results by starting with the highest-scoring player, giving them wins against lower-scoring players until their point total is reached, then proceeding to the next player. This greedy construction automatically satisfies logicality. The main approach is preferable because it begins from an arbitrary tournament, showing that any existing tournament can be converted into a logical one, thus proving a stronger statement and providing a constructive method for transforming tournaments without changing their score distribution.