China Girls' Mathematical Olympiad

Note that if there are $2m-4$ players, we can label them $$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 $P_i$ beats player $P_j$ if and only if $i>j$, and $A_{m-2}$ and $B_{m-2}$ are in a tie. It is easy to see that in the group of $m$ players, there exists a unique player $P_i$ with the maximum index $i$ ($m-1\le i\le 2m-5$, and this player won all games against other players in the group), and there exists a unique player $P_i$ with the minimum index $j$ ($1\le i\le m-3$, and this player lost all games against other players in the group). Hence this tournament has property $P(m)$ and not all players have distinct total points. If $n<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-3$. It suffices to show the following claim: If there are $2m-3$ players in a tournament with property $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 $n$-player ($n\ge m$) tournament with property $P(m)$, there is a complete winner.

Proof: We implement an induction on $n$. If $n=m$, the statement is trivial. Now assume that the statement is true for some $n=k$ ($k\ge m$), we consider a ($k+1$)-player tournament with property $P(m)$. Let $a_1,\cdots ,a_{k+1}$ denote the players. By the induction hypothesis, we may assume that $a_{k+1}$ is the winner in the group $a_2,\cdots ,a_{k+1}$. We consider three cases: (a) If $a_{k+1}$ won the game against $a_1$, then $a_{k+1}$ is the complete winner; (b) If $a_{k+1}$ tied the game against $a_1$, then the group $a_1,a_2,\cdots ,a_{k-1},a_{k+1}$ has no winner, violating the condition that the tournament has property $P(m)$; (c) If $a_{k+1}$ lose the game against $a_1$, then the group $\{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 $a_1$. Thus $a_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 $n$-player ($n\ge m$) tournament with property $P(m)$, there is a complete loser.

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