I think this can be proved by following way;; Consider the tournament result as a directed graph. Note that every complete directed graph either has a full length cycle or can be divided into two sets $ A, B$ such that every edges between them are directed to $ B$. This can be proved by considering maximum cycle of the graph... If we apply this lemma repeatedly, we can divide a complete directed graph $ G$ into some cycles $ A_{1}, A_{2}, \cdots , A_{n}$ such that if $ i < j$, every edges among $ A_{i}, A_{j}$ are directed to $ A_{j}$, so it is enough to prove that each cycles have length less than $ M + 1$. If it can, we can get a desired arrangement of $ G$ by aligning points like $ A_{1}, A_{2}, A_{3}, \cdots$ and each points in the same cycle by the reverse order of original cycle. We'll prove that if there are no $ n$-cycle in a complete directed graph, any $ n + 1$-cycles also doesn't exist. if not so, let $ C$ be that cycle. Remove one point $ \{x\}$ in the $ C$. Applying the lemma to $ C/\{x\}$, we can divide it to $ A$, $ B$, which satisfies the fact mentioned above... because there are no full cycle. and by its definition, initial $ n + 1$-cycle should be in the form of $ x \rightarrow A \rightarrow B \rightarrow x$. Let $ a$ be the lastest point of $ A$ in the cycle. than the cycle would proceed as $ a \rightarrow b_{1} \rightarrow b_{2} \rightarrow \cdots$. However, there is also $ a \rightarrow b_{2}$, and this reduces the length of the cycle by 1. This contradicts the assumption...

Little Gauss wrote: I think this can be proved by following way;; Consider the tournament result as a directed graph. We'll prove that if there are no $ n$-cycle in a complete directed graph, any $ n + 1$-cycles also doesn't exist. ... Dear Little Gauss, nice solution! In fact there is always at least one chain passing all the points in a complete graph.Then by the lemma above we get the proof immediately.

We prove the result by induction on $M$ and $N$. Notationally, we say $p_1>p_2$ if player $p_1$ beats player $p_2$. Suppose that $M=2$. Then the relation between players is transitive, which easily implies that they can be uniquely ordered. Rigorously, take the player with the most wins, and note that by transitivity if any player beat the first, the second player would have strictly more wins. So there is an undefeated player, and the result follows by induction on the rest of the tournament. Now suppose $M>2$. The condition is equivalent to there being no $M+1$ cycle. We now split up the proof into two cases. Case 1: There is an $M$-cycle $v_1>v_2>\cdots > v_M>v_1$, denoted $C$, in the tournament. Consider some $w$ not in $C$. If $w>v_i$ for some $i$, then \[ w>v_i>v_{i+1}>\cdots >v_{i-1} \]This is a cycle of length $M+1$, where the indices are taken modulo $M$, so $w>v_{i-1}$. But from $w>v_i\implies w>v_{i-1}$ it easily follows that if $w>v_1$, then $w>v_i$ for all $i$. Similarly, if $w<v_1$, then $w<v_i$ for all $i$. Thus we can partition the tournament into sets $A,B,C$, where $A$ beats all members of $C$, $C$ beats all members of $B$, and $a+b+M=N$, where $a$ and $b$ are the sizes of $A$ and $B$. Now for any member $x$ of $A$ and any member $y$ of $B$, $x>v_1>v_2>\cdots >v_{m-1}>y$, so $x>y$. We now assign the labels $\{1,\cdots b\}$ to $B$, $\{b+1,\cdots N-a\}$ to $C$, and $\{N-a+1,\cdots N\}$ to $A$. By the inductive hypothesis, we can assign some relative ordering of the labels in each set that is internally consistent with the desired property of the problem in both $A$ and $B$, and we can label $C$ arbitrarily in an internally consistent way, as long as the player labelled $M$ beats the player labelled $1$. Also, as all members of $A$ beat all members of $C$ which beat all members of $B$, the property $a\ge b+M-1\implies$ player $a$ beats $b$ is vacuously true between two members of any two of $A,B,C$. Thus we can construct a valid labelling. Case 2: There is no $M$-cycle. Then by the inductive hypothesis on $M$, we can label the players in such a way that $a\ge b+M-2$ implies $a$ beats $b$, a strictly stronger condition than the one needed.

Dear Little Gauss,your soluntion is very nice.But actually we can't always divide a complete directed graph without a full length cycle into two sets A,B such that every edges between them are directed to B

Tanyingjie wrote: But actually we can't always divide a complete directed graph without a full length cycle into two sets A,B such that every edges between them are directed to B Yes you can. Consider any maximal cycle $C$, say \[ v_1 \to v_2 \to \dots \to v_k \to v_1. \]By maximality, this means we cannot have $v_i \to w \to v_{i+1}$ for any $i$ and any vertex $w \notin C$. It follows that for any $w \notin C$, either $v_i \to w$ for every $i$, in which case we say $w$ is weak, or $w \to v_i$ for every $i$, in which case we say $w$ is strong. It then follows that every strong vertex beats every weak vertex too (if $w$ is strong and $x$ is weak, then $w \to v_1 \to \dots \to v_k \to x$ is a path). Since $C$ wasn't the entire graph, there is either at least one strong or at least one weak vertex. Done. [asy][asy] size(6cm); dotfactor *= 1.5; pair A = dir(90); pair B = dir(210); pair C = dir(330); dot("$v_1$", A, A, red); dot("$v_2$", B, B, red); dot("$v_3$", C, C, red); draw(A--B, red, EndArrow, Margin(2,2)); draw(B--C, red, EndArrow, Margin(2,2)); draw(C--A, red, EndArrow, Margin(2,2)); draw(ellipse( (2.6,0.3), 0.6, 1.6), blue); draw(ellipse( (-2.6,0.3), 0.6, 1.6), blue); draw((1,0.3)--(2,0.3), blue+1, EndArrow, Margin(2,2)); draw((-2,0.3)--(-1,0.3), blue+1, EndArrow, Margin(2,2)); draw((-2.3,-1.2)--(2.3,-1.2), blue+dashed, EndArrow, Margin(2,2)); dot((2.8,0.7), blue); dot((2.7,1.2), blue); dot((2.5,0.1), blue); dot((-2.8,0.7), blue); dot((-2.7,-1.0), blue); dot((-2.3,0.1), blue); [/asy][/asy] Incidentally, this is also the main idea underlying pi37's solution, which is the same as my own. Rather than taking $C$ to be a maximal cycle we take $C$ to be an $M$-cycle which also solves the problem.

MellowMelon wrote: Let $ N > M > 1$ be fixed integers. There are $ N$ people playing in a chess tournament; each pair of players plays each other once, with no draws. It turns out that for each sequence of $ M + 1$ distinct players $ P_0, P_1, \ldots P_M$ such that $ P_{i - 1}$ beat $ P_i$ for each $ i = 1, \ldots, M$, player $ P_0$ also beat $ P_M$. Prove that the players can be numbered $ 1,2, \ldots, N$ in such a way that, whenever $ a \geq b + M - 1$, player $ a$ beat player $ b$. Gabriel Carroll. We induct on $N>M>1$. For $M=2$, pick a player $v$, then partition the remaining players in two groups $A, B$ so that $\overrightarrow{va}, \overrightarrow{bv}$ are edges for all $a, b \in A, B$ respectively. The condition ensures that $\overrightarrow{ba}$ is an edge for all $a \in A, b \in B$. Hence, we can label $B$ with $1, 2, \dots, |B|$ by induction on $N$ and $A \cup \{v\}$ by $|B|+1, \dots, N$, so that both are internally satisfied. This provides a valid labelling. Now for the induction step. For fixed $N$, suppose $1<M<N$ is the smallest integer with this property. Claim. The maximal cycle has size at least $M$. (Proof) Pick two points $P_0, P_d$ with the maximum graph theoretic distance. Then $P_0 \rightarrow P_1 \rightarrow \dots \rightarrow P_d$; so $d>1 \implies P_d \rightarrow P_0$ then we have a $(d+1)$ cycle. If $d<M-1$ then for any chain $P_0 \rightarrow P_1 \rightarrow \dots \rightarrow P_{M-1}$ we have $P_0 \rightarrow P_{M-1}$ contradicting the minimality of $M$. Hence, $(d+1) \ge M$, as desired. Now we pick this maximal cycle $\mathcal{C}$. For any vertex $u$ if we can find $u, w \in \mathcal{C}$ with $\overrightarrow{vu}, \overrightarrow{wv}$ as edges then it is possible to append $v$ in $\mathcal{C}$. So for all $v \not \in \mathcal{C}$ all edges between $v$ and vertices of $\mathcal{C}$ have the same direction. Suppose $A$ is the set of those vertices where these edges lead inwards and $B$ where they lead outwards. For any $a \in A, b \in B$, if $\overrightarrow{ab}$ is an edge, then we have a directed path $a \rightarrow b \rightarrow v_1 \rightarrow \dots \rightarrow v_{M-1}$ for $v_1 \rightarrow \dots$ as a chain of $\mathcal{C}$, so $a \rightarrow v_{M-1}$, a contradiction! Thus, all players outside $A$ defeat everyone in $A$ (if $A$ is empty, $\mathcal{C}$ fits this role). Labelling $1, \dots, |A|$ to vertices in $A$ in a suitable way, we can translate a natural labelling of the remaining vertices by $|A|$.

The following claim solves the problem easily: In each tournament, either there is a hamiltonian cycle or the participants can be partitioned into two nonempty sets $A,B$ auch that each player in $A$ beats each player in $B$. Edit: I see it is Little Gauss’s solution.

Did this in November and posting this now... I will use two lemmas. Lemma 1(Very standard) There exists a path of length $N-1$. We proceed by strong induction. Suppose $v\rightarrow v_1,\cdots,v_k$. Then by inductive hypothesis, there is a path of length $k-1$ in $v_1,\cdots,v_k$ and a path of length $N-k-2$ in the other $N-k$ vertices. Hence the path (length $N-k-2\rightarrow v\rightarrow $ path of length $k-1$) works. Hence we can take this path and label $v_N\rightarrow v_{N-1}\rightarrow \cdots \rightarrow v_1$. To finish the problem, we use the following lemma. Lemma 2. There exists no cycle of length $\ge M$. We instead show if there exist a cycle of length $x+1$ then there is a cycle of length $x$ for $x\ge 3.$ Consider the paths $v_{i}\rightarrow v_{i+3}\rightarrow v_{i+4}\rightarrow \cdots \rightarrow v_{i-1}\rightarrow v_{i+2}\rightarrow v_{i}$. For these paths to not exist, $v_{2i}\rightarrow v_{2i\pm 3}$ for all $i$ or $v_{2i\pm 3}\rightarrow v_{2i} $. This gives a contradiction if $l$ is odd. We will deal with the case $l$ is even and $l\ge 8$. For $l=4$, we can't even deal with $v_2\rightarrow v_0\rightarrow v_2$, so it is okay. For $l\ge 8$, the cycle $v_0\rightarrow v_3\rightarrow v_1\rightarrow v_2\rightarrow v_5\rightarrow v_6\rightarrow v_7\rightarrow \cdots \rightarrow v_{l-1}\rightarrow v_0$ works. Notice how $v_4$ is not in the cycle. Therefore, taking the longest path $v_n\rightarrow v_{n-1}\rightarrow \cdots \rightarrow v_1$, and labelling $v_i$ with $i$ indeed works.

Twitch lemma unit Note that this implies no cycles of length $M+1$ or larger exist. Let $C$ be the cycle of maximal length. Then the rest of vertices can be partition into $A \sqcup B$ where $A$ points into $C$ and $C$ points into $B$. Since $C$ has length at most $M$, we can solve this inductively for $A, B, C$ and sort them in that order.

We view the this as a directed tournament on $N$ vertices, we know that there exists a hamiltonian path as this is a tournament. We also know that there are no cycles of length $M$ thus from twitch lemma we know there are no cycles of length $>M$, thus take the hamiltonian path and the result becomes clear.