\section*{Problem 8}

There are 21 towns. Each airline runs direct flights between every pair of towns in a group of five. What is the minimum number of airlines needed to ensure that at least one airline runs direct flights between every pair of towns?


\section*{Solution}

Answer: 21.

There are 210 pairs of towns. Each airline serves 10 pairs, so we certainly need at least 21 airlines. The following arrangement shows that 21 is possible:

\begin{tabular}{rrrr}
2 & 3 & 4 & 5 \\
6 & 7 & 8 & 9 \\
10 & 11 & 12 & 13 \\
14 & 15 & 16 & 17 \\
18 & 19 & 20 & 21 \\
6 & 10 & 14 & 18 \\
7 & 11 & 15 & 19 \\
8 & 12 & 16 & 20 \\
9 & 13 & 17 & 21 \\
6 & 11 & 16 & 21 \\
7 & 10 & 17 & 20 \\
8 & 13 & 14 & 19 \\
9 & 12 & 15 & 18 \\
6 & 12 & 17 & 19 \\
7 & 13 & 16 & 18 \\
8 & 10 & 15 & 21 \\
9 & 11 & 14 & 20 \\
6 & 13 & 15 & 20 \\
7 & 12 & 14 & 21 \\
8 & 11 & 17 & 18 \\
9 & 10 & 16 & 19
\end{tabular}

