Problem 1680

The answer is $k = 4$. If $k = 3$ was possible, then every player plays either 2 or 3 games against each of the other 23 players. Hence he plays at least $2 \cdot 23 = 46$ and at most $3 \cdot 23 = 69$ games. It is impossible that there is a player $A$ who has played 46 games (and hence 2 games against every other player) and simultaneously a player $B$ who has played 69 games (and hence 3 games against every other player, and in particular against $A$). Hence there are only 23 numbers available in the range 46, 47, $\ldots,$ 69, which yields a contradiction.

To prove that $k = 4$ is possible we argue by mathematical induction. We show that for every $n \ge 3$ there exists a tournament $T_n$ with $n$ players, where every pair of players plays at least two and at most four games against each other, and where every player plays a different number of games. For $n = 3$ consider three players that play respectively 2, 3, and 4 games against each other; then they play respectively a total of 5, 6, and 7 games.

In the inductive step we consider the tournament $T_n$ where the players have played $a_1 < a_2 < \dots < a_n$ games.

(i) If in $T_n$ no players has played exactly two games against every other player, then $a_1 > 2n - 2$. We create a new player and make him play exactly two games against every other player. The new numbers are $2n < a_1 + 2 < a_2 + 2 < \dots < a_n + 2$.

(ii) Otherwise, no player in $T_n$ can have played exactly four games against every other player, and hence $a_n < 4n - 4$. We create a new player and make him play exactly two games against every other player. The new numbers are $a_1 + 4 < a_2 + 4 < \dots < a_n + 4 < 4n$.

$\square$