20 cities and 2 airline companies
Source: Portugal OPM 1997 p3
May 18, 2024
combinatorics
Problem Statement
In Abaliba country there are twenty cities and two airline companies, Blue Planes and Red Planes. The flights are planned as follows:
Given any two cities, one and only one of the two companies operates direct flights (in both directions and without stops) between the two cities. Furthermore:
There are two cities A and B between which it is not possible to fly (with possible stops) using only Red Planes.
Prove that, given any two cities, a passenger can travel from one to the other using only Blue Planes, making at most one stop in a third city.