Problem:
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?
Solution
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:
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 1 | 6 | 7 | 8 | 9 |
| 1 | 10 | 11 | 12 | 13 |
| 1 | 14 | 15 | 16 | 17 |
| 1 | 18 | 19 | 20 | 21 |
| 2 | 6 | 10 | 14 | 18 |
| 2 | 7 | 11 | 15 | 19 |
| 2 | 8 | 12 | 16 | 20 |
| 2 | 9 | 13 | 17 | 21 |
| 3 | 6 | 11 | 16 | 21 |
| 3 | 7 | 10 | 17 | 20 |
| 3 | 8 | 13 | 14 | 19 |
| 3 | 9 | 12 | 15 | 18 |
| 4 | 6 | 12 | 17 | 19 |
| 4 | 7 | 13 | 16 | 18 |
| 4 | 8 | 10 | 15 | 21 |
| 4 | 9 | 11 | 14 | 20 |
| 5 | 6 | 13 | 15 | 20 |
| 5 | 7 | 12 | 14 | 21 |
| 5 | 8 | 11 | 17 | 18 |
| 5 | 9 | 10 | 16 | 19 |
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.