Maths Olympiad Prep

Library / China Girls' Mathematical Olympiad /51 of 51

China Girls' Mathematical Olympiad

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it China

In a round robin chess tournament each player plays with every other player exactly once. The winner of each game gets 11 point and the loser gets 00 point. If the game ends in a tie, each player gets 0.50.5 point. Given a positive integer mm, a tournament is said to have property P(m)P(m) if the following holds: among every set SS of mm players, there is one player who won all his games against the other m−1m-1 players in SS and one player who lost all his games against the other m−1m-1 players in SS.

For a given integer m≥4m \ge 4, determine the minimum value of nn (as a function of mm) such that the following holds: in every nn-player round robin chess tournament with property P(m)P(m), the final scores of the nn players are all distinct.

Solution

Note that if there are 2m−42m-4 players, we can label them
a1,a2,…,am−3,Am−2,Bm−2,am−1,…,a2m−5, a_1, a_2, \dots, a_{m-3}, A_{m-2}, B_{m-2}, a_{m-1}, \dots, a_{2m-5},
and assume that player PiP_i beats player PjP_j if and only if i>ji > j, and Am−2A_{m-2} and Bm−2B_{m-2} are in a tie. It is easy to see that in the group of mm players, there exists a unique player PiP_i with the maximum index ii (m−1≤i≤2m−5m-1 \le i \le 2m-5, and this player won all games against other players in the group), and there exists a unique player PiP_i with the minimum index jj (1≤i≤m−31 \le i \le m-3, and this player lost all games against other players in the group). Hence this tournament has property P(m)P(m) and not all players have distinct total points. If n<2m−4n < 2m-4, we can then build a similar tournament by taking players away from both ends index-wise). Hence the answer is greater than 2m−32m-3. It suffices to show the following claim:
If there are 2m−32m-3 players in a tournament with property P(m)P(m), then the players must have distinct total final score.

In a group, if a player won (or lose) all games against the rest of the players in the group, we call this player the winner (or loser) of the group. If a player won (or lose) all his games in the tournament, we call this player the complete winner (or complete loser). We establish the following lemmas.

Lemma 1 In an nn-player (n≥mn \ge m) tournament with property P(m)P(m), there is a complete winner.

Proof: We implement an induction on nn. If n=mn=m, the statement is trivial. Now assume that the statement is true for some n=kn=k (k≥mk \ge m), we consider a (k+1k+1)-player tournament with property P(m)P(m). Let a1,⋯ ,ak+1a_1, \cdots, a_{k+1} denote the players. By the induction hypothesis, we may assume that ak+1a_{k+1} is the winner in the group a2,⋯ ,ak+1a_2, \cdots, a_{k+1}. We consider three cases:
(a) If ak+1a_{k+1} won the game against a1a_1, then ak+1a_{k+1} is the complete winner;
(b) If ak+1a_{k+1} tied the game against a1a_1, then the group a1,a2,⋯ ,ak−1,ak+1a_1, a_2, \cdots, a_{k-1}, a_{k+1} has no winner, violating the condition that the tournament has property P(m)P(m);
(c) If ak+1a_{k+1} lose the game against a1a_1, then the group {a1,a2,⋯ ,ak−1,ak,ak+1}∖{ai}(2≤i≤k)\{a_1, a_2, \cdots, a_{k-1}, a_k, a_{k+1}\} \setminus \{a_i\} (2 \le i \le k) has a winner, and this winner can only be a1a_1. Thus a1a_1 is the complete winner.
Combining the three cases, we find a complete winner in the tournament, hence our induction is complete.

In exactly the same way, we can prove that

Lemma 2 In an nn-player (n≥mn \ge m) tournament with property P(m)P(m), there is a complete loser.

Now we are ready to prove our claim in a similar manner.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.