Problem 1808

First, we show that for each contestant at most one game ended in a draw. Assume, to the contrary, that the contestant $A$ tied against $B$ and $C$. The game between $A$ and $B$ was tied, so $C$ won against at least one of them. The game between $A$ and $C$ was tied, so $C$ won against $B$. On the other hand, the game between $A$ and $C$ ended in a draw, but $B$ did not beat either of them. This contradicts the assumptions of the problem.

The sequence of contestants $A_1, A_2, \ldots, A_k$ is called increasing, if for all $i = 1, \ldots, k-1$ the contestant $A_i$ lost against $A_{i+1}$. Let $n$ be the length of the longest increasing sequence of contestants. If $n = 64$, then we are done. Otherwise, assume that $n < 64$.

Let $B$ be the contestant who is not included in the longest increasing sequence $A_1, A_2, \ldots, A_n$. Then $A_1$ did not win against $B$, otherwise $B, A_1, A_2, \ldots, A_n$ would be an increasing sequence of length $n+1$. Assume that $B$ won against $A_1$. Then $B$ and $A_2$ did not tie since $A_1$ lost against both of them. If $A_2$ had won against $B$, then $A_1, B, A_2, \ldots, A_n$ would be an increasing sequence of length $n+1$. So, $B$ won against $A_2$. Similarly, we conclude that $B$ won against $A_3, A_4, \ldots, A_n$. So, $A_1, A_2, \ldots, A_n, B$ is an increasing sequence of length $n+1$, a contradiction.

Hence, $B$ and $A_1$ tied. As $A_1$ tied against at most one opponent, we have $n-1=63$ and this opponent is $B$. If $B$ won against $A_2$, we can repeat the argument above to show that $B$ also won against $A_3, A_4, \ldots, A_{63}$. So, $A_1, A_2, \ldots, A_{63}, B$ is an increasing sequence of length 64. We have assumed no such sequence exists, so $A_2$ must have beaten $B$ (they did not tie as $B$ tied against $A_1$). Similarly, we conclude that each of the remaining contestants $A_i$ for $3 \le i \le 63$ has won against $B$. On the other hand, there were two other players, $A_i$ and $A_j$ for $i \ne j$, $i, j > 2$, whose game ended in a draw. This means they both won against $B$. The latter contradicts the assumptions of the problem, which proves that the length of the longest increasing sequence of players is 64.

As in the first solution we show that each participant tied at most once. Let $A = B$ denote a tie. If $A$ won, we write $A \to B$. If $B$ won, we write $A \leftarrow B$. If $A = B$, then for all other contestants $C$ we have either $C \to A$ or $C \to B$.

If $A = B$, $C = D$ and $A \to C$, then $C \to B$. Since $C = D$, we have $B \to D$, and since $A = B$, we have $D \to A$.

Assume that $k$ games ended in a draw. We use induction to show that the $2k$ players who tied once can be labeled as $A_1, A_2, \dots, A_{2k}$ in such a way that

$$A_1 \to A_2 \to A_3 \to \dots \to A_{2k} \to A_1 \text{ and } A_i = A_{i+k} \text{ for } i = 1, \dots, k. \quad (1)$$

If $k=2$, denote the 4 players by $A=B$, $C=D$. Without loss of generality we may assume that $A \to C$. As we have shown before, we can assign the labels as follows: $A_1 = A$, $A_2 = C$, $A_3 = B$ and $A_4 = D$.

Assume that (1) holds and let us show this in the case of $k-1$ tied games. Let us choose a pair of contestants who tied against one another and denote them by $C$ and $D$. The remaining $2k$ contestants can be labeled so that (1) holds. Furthermore, we may also assume that $A_1 \to C$ (otherwise exchange $C$ and $D$). Since $A_1 = A_{k+1}$, we have $C \to A_{k+1}$. Let $i$ be the smallest index, such that $C \to A_{i+1}$. Then $A_i \to C \to A_{i+1}$. On the other hand, $A_i = A_{i-k-1}$, $C = D$ and $A_{i+1} = A_{i+k+1}$. As shown above, this implies $A_{i+k} \to D \to A_{i+k+1}$.

Let $B_j = A_j$ for $1 \le j \le i$, $B_{i+1} = C$, $B_j = A_{j-1}$ for $j = i+2, \dots, i+k+1$, $B_{i+k+2} = D$ and $B_j = A_{j-2}$ for $j \ge i+k+3$. Then
$$B_1 \to B_2 \to B_3 \to \dots \to B_{2k+2} \to B_1 \text{ and } B_j = B_{j+k+1} \text{ for } j = 1, \dots, k+1,$$
which is what we wanted to see.