Determine the least integer $k$ for which the following story could hold true: In a chess tournament with $24$ players, every pair of players plays at least $2$ and at most $k$ games against each other. At the end of the tournament, it turns out that every player has played a different number of games.
Problem
Source: MMC 2013
Tags: induction, combinatorics proposed, combinatorics
14.06.2013 17:24
In fact when we do the same problem for $0$ to $k-2$ games in the Tournament, the result will be the same. (everyone plays only $46$ games more) If $k=3$ it is impossible in the tournament, as we would have in the Tournament that each number from $0$ to $23$ happens once. So one plays to everyone and another player didn't play at all. contradiction. For $k=4$ : let $a_{23-k}$ plays to $a_k$ to $a_{23-k-1}$ for $k$ from $0$ to $11$ and then yet $a_{23}$ to $a_{12}$ to $a_{22}$ again in the Tournament. (so yet everyone plays twice to each other in the normal tournament) This satisfy the condition. ** I hope I understand the question right and so it was quite trivial.
17.06.2013 11:45
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\cdot23=46$ and at most $3\cdot23=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. The proof that $k=4$ is possible is done by induction: We show that for every $n\ge3$ 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<\cdots<a_n$ games. (i) If in $T_n$ no player 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<\cdots<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 four games against every other player. The new numbers are $a_1+4<a_2+4<\cdots<a_n+4<4n$.