Problem 2017

Solution:

We first give an example of a league with $\frac{n^{3}}{8}-\frac{n^{2}}{4}$ teams.

Split the colours in two sets of size $n / 2$. Let $m = n / 2$ and let $c_{1}, \ldots, c_{m}$ and $d_{1}, \ldots, d_{m}$ be the colours in those sets.

Consider all pairs of kits of the form $\left(\{c_{i}, c_{j}\}, d_{k}\right)$ or $\left(\{d_{i}, d_{j}\}, c_{k}\right)$, where $i < j$ and $1 \leq i, j, k \leq m$. There are $2 \cdot \binom{m}{2} \cdot m = m^{3} - m^{2} = \frac{n^{3}}{8} - \frac{n^{2}}{4}$ such pairs of kits. We claim that this construction is valid.

Consider any pair of kits $\left(\{c_{i}, c_{j}\}, d_{k}\right)$. Then for any other team of the form $\left(\{c_{a}, c_{b}\}, d_{u}\right)$, the kit $d_{u}$ is not clashing with the home kit $\{c_{i}, c_{j}\}$. Furthermore, for any team of the form $\left(\{d_{a}, d_{b}\}, c_{u}\right)$ the kit $\{d_{a}, d_{b}\}$ is not clashing with the home kit $\{c_{i}, c_{j}\}$. Thus, the construction is valid.

We now prove that there is no larger league. Consider any colour $c$. Take any other colour $d$. If there is a team whose home kit is $\{c, d\}$, then there is no team whose home kit contains $c$ and whose away kit is $d$. Conversely, if there is a team whose home kit contains $c$ and whose away kit is $d$, then there is no team whose home kit is $\{c, d\}$.

Let $A(c)$ be the number of colours $d$ such that there is a home kit of the form $\{c, d\}$, and let $B(c)$ the number of colours $d$ such that there is a team whose home kit contains $c$ and whose away kit is $d$.

From the observation we made, $A(c) + B(c) \leq n - 1$. The number of teams whose home kit contains the colour $c$ is at most
$$A(c) B(c) \leq \frac{n-2}{2} \cdot \frac{n-1}{2} = \frac{n^{2}}{4} - \frac{n}{2}$$
where the inequality follows from the fact that the function $x \mapsto x(n-1-x)$ is increasing on $(0, (n-1)/2)$ and decreasing on $((n-1)/2, n-1)$.

Summing up over all colours $c$ and dividing by 2 since we counted each home kit twice, we obtain that the number of teams is at most
$$\frac{1}{2} \sum_{c} A(c) B(c) \leq \frac{n}{2} \cdot \left(\frac{n^{2}}{4} - \frac{n}{2}\right) = \frac{n^{3}}{8} - \frac{n^{2}}{4}.$$