, 2009

Write $P \succ Q$ if player $P$ beat player $Q$.

Lemma 1. Any set of $K > 1$ players can be arranged in a sequence $P_1, \dots, P_K$ such that $P_1 \succ P_2 \succ \dots \succ P_K$.

Proof. Let $P_1 \succ \dots \succ P_J$ be the longest such sequence that can be formed from any subset of the given players, and suppose for contradiction that some player $Q$ among the $K$ players does not appear in the sequence. If all of $P_1, \dots, P_J$ beat $Q$, we append $Q$ to the end of the sequence. Otherwise, there exists a smallest $i$ such that $Q \succ P_i$, and then we can insert $Q$ into the sequence just before $P_i$. Either way, we have created a sequence of length $J+1$, contradicting the maximality of $J$. $\square$

Now, we will prove the problem statement for all $N \ge 0$ by induction. For the base case, if $N < M$, just assign numbers arbitrarily, and the conclusion holds vacuously.

Now suppose the result holds for any number of players less than $N$; we will show it for $N$ players. Let $P$ be the player who beat the most opponents. If $P$ beat all other players, we can assign $P$ the number $N$ and use the induction hypothesis for the remaining players. So we may assume $P$ was beaten by $K \ge 1$ other players.

Define a top-cycle of order $L$ to be a sequence $C_L = (P_0, \dots, P_L)$ of players such that

* $P_0 \succ P_1 \succ P_2 \succ \dots \succ P_L \succ P_0$;
* $P_L = P$;
* all players not in the sequence were beaten by $P$.

We will construct a top-cycle $C_{K+1}$ of order $K+1$. By the lemma, the players who beat $P$ can be arranged into a sequence $P_1, \dots, P_K$ such that $P_{i-1} \succ P_i$ for each $i$. Let $P_{K+1} = P$. Notice that there exists a player $P_0$ such that $P \succ P_0 \succ P_1$: otherwise, $P_1$ beat every player beaten by $P$ and also beat $P_2$, so $P_1$ beat more players than $P$, contradicting the choice of $P$. This choice of $P_0$ completes the construction of $C_{K+1}$.

We also claim that $K+1 < M$. We approach indirectly by assuming $K+1 \ge M$. Then for each $Q$ that was beaten by $P$, either $Q = P_0$ or $Q$ is not in $C_{K+1}$. Either way, we have $P_{K-M+2} \succ P_{K-M+3} \succ \dots \succ P_{K+1} \succ Q$, and then $P_{K-M+2} \succ Q$ by the given. But we also have $P_{K-M+2} \succ P_{K-M+3}$. Therefore, $P_{K-M+2}$ beat every player who was beaten by $P$ and at least one more player, again contradicting the choice of $P$.

Now, given a top-cycle $C_L$ of any order $L$, we claim that either all players in the cycle beat all players not in the cycle, or else we can insert another player to form a top-cycle $C_{L+1}$ of order $L+1$. Indeed, suppose some player $Q$ not in the cycle was not beaten by all players in the cycle. Take the smallest $i$ such that $Q$ beat $P_i$, and then inserting $Q$ just before $P_i$ gives us a top-cycle of order $L+1$. (If $i=0$ then we need to check that $P$ beat $Q$, but this follows from the fact that $C_L$ was a top-cycle.)

Start with $C_{K+1}$ and repeatedly expand the cycle as just described. Eventually we must reach a top-cycle $C_L$ such that all players in $C_L$ beat all players not in $C_L$, and then the expanding must stop. We claim that when this happens, $L < M$. To prove this, it suffices to show that if we ever reach a top-cycle of order $M-1$, then all players in the cycle beat all players not in the cycle (so that we can expand no further). So let $P_0 \succ P_1 \succ \dots \succ P_{M-1} = P$ be the top-cycle, and let $Q$ be any player outside the top-cycle. Then $P \succ Q$ and the given imply $P_0 \succ Q$. But then we also have $P_1 \succ P_2 \succ \dots \succ P_{M-1} \succ P_0 \succ Q$, implying $P_1 \succ Q$. Repeating this process, we get $P_i \succ Q$ for each $i$. This shows that all players in the cycle beat all players outside the cycle, as claimed.

This proves that there exists a top-cycle $C_L = (P_0, \dots, P_L)$ with $L < M$, such that all players in $C_L$ beat all players not in $C_L$.

Now use the induction hypothesis to assign the numbers $1, \dots, N-L-1$ to all players not in $C_L$. Assign the number $N-L$ to $P_1$ and assign the number $N$ to $P_0$. Finally, assign the remaining numbers $N-L+1, \dots, N-1$ arbitrarily to the rest of the players in $C_L$.

To check that this assignment meets the requirements, consider any $a, b$ with $a \ge b + M - 1$. If $a < N - L$, then we know that the player numbered $a$ beat the player numbered $b$ by the induction hypothesis. If $a \ge N - L$ and $b < N - L$, then player $a$ beat player $b$ because player $a$ is in $C_L$ and $b$ is not. And if $b \ge N - L$, then the only possibility is $L = M - 1, a = N, b = N - L$. In this case, player $a$ is $P_0$, player $b$ is $P_1$, and we know that $P_0 \succ P_1$.

(By Ricky Liu). Note that we may remove the condition $N > M$, since if $N \le M$, the claim is trivial. We will again write $P \succ Q$ if player $P$ beats player $Q$. We will prove the result by strong induction on $M$, and then on $N$ for fixed $M$.

We first prove the case $M = 2$. Note that $P \succ Q$ if and only if $P$ beat strictly more players than $Q$, for $P \succ Q$ implies $P$ beats $Q$ and everyone $Q$ beats. We therefore number the players in reverse order of the number of players they beat.

For $M > 2$, we may assume that there exists a set of players $B = \{P_0, \dots, P_{M-1}\}$ such that $P_0 \succ P_1 \succ \dots \succ P_{M-1} \succ P_0$, because otherwise the problem reduces to a smaller value of $M$. Let $A$ be the set of players that everyone in $B$ beats, and let $C$ be the set of players that beat everyone in $B$.

We claim that all players lie in $A$, $B$, or $C$. Indeed, if for $Q \notin B$, $P_{M-1} \succ Q$, then $P_0 \succ Q$, for we cannot have $P_0 \succ P_1 \succ \dots \succ P_{M-1} \succ Q \succ P_0$. Similarly, $P_0 \succ Q$ implies $P_1 \succ Q$ and so forth. Therefore, if $P_i \succ Q$ for any $i$, then $P_i \succ Q$ for all $i$. The claim follows easily. Also note that if $Q \in C$ and $R \in A$, then $Q \succ R$. Indeed, otherwise $Q \succ P_0 \succ P_1 \succ \dots \succ P_{M-2} \succ R \succ Q$.

If $A$ and $C$ are both empty, so that $N = M$, the result is easy. Otherwise, using the induction hypothesis on $N$, we can construct suitable numberings for each of $A$, $B$, and $C$. But then adding $|A|$ to all assigned numbers in $B$ and adding $|B|$ to all assigned numbers in $C$ gives a suitable numbering for all players.