Dutch Mathematical Olympiad

We will show that $5$ is the largest value of $n$ for which a balanced tournament with $n$ teams exists. First we will show that in a balanced tournament with $n\ge 5$ teams, there are no three teams that all play against one another in the tournament.

Suppose towards a contradiction that we can find three teams in a balanced tournament that all play against each other, say teams $A$, $B$ and $C$. Because $n\ge 5$ there are two other teams, say $D$ and $E$. Since $A$, $B$ and $C$ already play three matches between them, there are no other matches between the quadruple $A$, $B$, $C$ and $D$. In other words: $D$ does not play against $A$, $B$ and $C$. The same holds for team $E$. If we now consider the quadruple $A$, $B$, $D$ and $E$ we see that there are at most two matches: $A$ against $B$, and possibly $D$ against $E$. This means that we have found four teams such that there are not exactly three matches between these four teams. This is a contradiction.

Now we will show that a balanced tournament is not possible with $n\ge 6$ teams. Suppose that $n\ge 6$ and, towards a contradiction, that a balanced tournament with $n$ teams exists. We look at the first six teams, say teams $A$ to $F$. Suppose that $A$ plays against at most two of these teams, say at most against $B$ and $C$ but not against $D$, $E$ and $F$. Since three matches have to be played among the quadruple $A$, $D$, $E$ and $F$, the teams $D$, $E$ and $F$ all have to play against one another. This is in contradiction with our previous findings.

We conclude that $A$ has to play against at least three of the teams, for example $B$, $C$ and $D$. This gives three matches in the quadruple $A$, $B$, $C$, $D$, so $B$, $C$ and $D$ do not play any matches between them. Because the quadruple $B$, $C$, $D$, $E$ also has to play three matches, $E$ has to play against all of $B$, $C$ and $D$. But now we find a contradiction in the quadruple $A$, $B$, $C$, $E$: there are already four matches between these teams ($A$ against $B$, $A$ against $C$, $B$ against $E$, and $C$ against $E$). Therefore a balanced tournament with $n\ge 6$ does not exist.

To conclude, we will show that a balanced tournament with five teams exists. To make such a tournament, imagine the teams are standing in a circle. Two teams play against each other if they are standing next to each other in the circle. If we look at any quadruple of teams, we see there are exactly three pairs of teams standing next to each other in the circle. So the four teams plays three matches between them. We conclude that $5$ is the largest value of $n$ for which a balanced tournament with $n$ teams exists. □