In a certain country, there are exactly 2019 cities and between any two of them, there is exactly one direct flight operated by some airline, that is, given cities $A$ and $B$, there is either a flight from $A$ to $B$ or a flight from $B$ to $A$. Find the smallest number of airlines operating in the country, knowing that the direct flights between any three distinct cities are operated by different airlines.

#
Solution

The answer is 2019. Since there are 1009 disjoint pairs of cities, each airline can operate on at most 1009 pairs. There are exactly 2019 $\cdot$ 2018/2 direct flights, so the number of airlines is at least $\frac{2019 \cdot 2018}{2 \cdot 1009}=2019$. It remains to exhibit an example to verify that this number is indeed possible. Denote the cities by $c_{1}, c_{2}, \ldots, c_{2019}$ and the airlines by $f_{1}, f_{2}, \ldots, f_{2019}$. Connect cities $c_{i}$ and $c_{j}$ by a flight of airline $f_{l}$ if the remainder of $i+j$ divided by 2019 is $l$. To verify that this choice of airlines satisfies the statement, consider any three cities $c_{i}, c_{j}$, and $c_{k}$. For the same airline to operate on two pairs of them, in the set

$$
\{i+j, i+k, k+j\}
$$

there must be two numbers with the same remainder when divided by 2019. Suppose these two numbers are $i+j$ and $i+k$. The difference between them will then be a multiple of 2019, and we can write, for some integer $m$, that

$$
j-k=(i+j)-(i+k)=2019 \cdot m
$$

Since $j, k \in\{1,2,3, \ldots, 2019\}$ are distinct, $|j-k| \in\{1,2,3, \ldots, 2018\}$. This set does not contain any multiple of 2019, and consequently, the last equation has no solution. This shows that in this distribution, the airlines operating the direct flights between any three cities are distinct.