We consider sports tournaments with $n \ge 4$ participating teams and where every pair of teams plays against one another at most one time. We call such a tournament balanced if any four participating teams play exactly three matches between themselves. So, not all teams play against one another. Determine the largest value of $n$ for which a balanced tournament with $n$ teams exists.
Problem
Source: Dutch NMO 2021 p2
Tags: combinatorics
28.12.2021 22:16
The answer is $n=5$. We note the following lemma: if $n\geq 5$, there can't exist any triangle (three teams having met each other) or any antitriangle (three teams none of which faced any other) Proof: Wlog assume it is a triangle (otherwise switch all edges of the graph), involving the teams $A,B,C$ and consider two other vertices $D,E$. By the hypothesis neither of $D$ or $E$ has ever played with any of $A,B,C$. So, considering $ABDE$ we have a contradiction since there can be at most two teams having met. By our lemma, this means that all four teams are connected in a way such as $AB,BC,CD$ (call this a path). Considering five vertices $A,...,E$, we have wlog that $ABCD$ form a path (in this order. Considering $B,C,D,E$, they must be connected in that order (they would otherwise create a triangle or an anti triangle. Similarly $E$ must be connected to $A$, creating so a pentagon (which is an example which indeed works for $n=5$). Now assume there is a sixth point $F$. By considering $ABCF$, there must be at least one edge of the form $FA,FB,FC$, which is a contradiction because it creates an antitriangle. Therefore $n=5$ is the maximum, which is attainable with a pentagon.