Mattis is hosting a badminton tournament for $40$ players on $20$ courts numbered from $1$ to $20$. The players are distributed with $2$ players on each court. In each round a winner is determined on each court. Afterwards, the player who lost on court $1$, and the player who won on court $20$ stay in place. For the remaining $38$ players, the winner on court $i$ moves to court $i + 1$ and the loser moves to court $i - 1$. The tournament continues until every player has played every other player at least once. What is the minimal number of rounds the tournament can last?
Problem
Source: 2022 Baltic Way p6
Tags: combinatorics
Tintarn
28.11.2022 15:15
$39$
It is clear that we need at least $39$ rounds since each player has to play $39$ games. So it all hinges on giving a construction.
Here is one: Write the players in a $2 \times n$ table where each row is a court. Initially, put $1,2,\dots,n$ in the first column from top to buttom, and then $n+1,\dots,2n$ in the second column from buttom to top.
Now let $2n$ win all her games and hence remain in her spot.
Let all the other player rotate cyclically by one step clockwise in each round. It is clear that this can be achieved, by letting always the player in the first column win except for the first court (and moving players on the last court).
Moreover it is easy to see that any two players play each other this way. This is clear for any pairing involving player $2n$.
Any other pair of players can be written as $(x,x+2k-1)$ where we read modulo $2n-1$ and $k<n$. Now when $x$ is in the second column in the $k$-th last row, she will face player $x+2k-1$ as desired.