Problem 9. In a football championship, 16 teams participate, each playing against each other once. What is the minimum number of games that must be played so that among any three teams, there are two that have already played against each other?

#
# Answer: 56 games.

Solution. We will consider the games that have not been played. The condition means that there will be no three teams that have not played against each other at all. We will prove by induction on $k$ that for $2k$ teams, the maximum number of unplayed games is no more than $k^2$.

Base case: $k=1$ (the estimate is obvious).

Inductive step: Suppose it is proven for $k$, we will prove for $k+1$. If there are no unplayed games, then everything is proven. Otherwise, select any teams $A$ and $B$ that have not played against each other. Note that the number of unplayed games involving teams $A$ or $B$ is no more than $2k$ (not counting the game between $A$ and $B$), because for any team $C$, at least one of the games $AC$ or $BC$ has been played. Now consider all teams except $A$ and $B$ and apply the inductive hypothesis - among them, no more than $k^2$ games have not been played. Therefore, the total number of unplayed games is no more than $k^2 + (2k + 1) = (k+1)^2$, which is what we needed to prove.

Substituting $k=8$ gives that the number of unplayed games is no more than 64, and the total number of possible games is $\frac{16 \cdot 15}{2} = 120$, so the number of played games is no less than $120 - 64 = 56$.

The estimate is achieved if the teams are divided into two equal groups, all matches are played within each group, and no matches are played between the groups.