1983 cities are served by ten airlines. All services are both ways. There is a direct service between any two cities. Show that at least one of the airlines can offer a round trip with an odd number of landings.
Solution
Solution by Demetres Christofides
We show by induction that if n airlines serve more than 2n cities then at least one offers an odd round trip. For n = 1, this is trivial (there are at least 3 cities, all served by a single airline, so we have a round trip around 3 cities).
Suppose the result is true for n. For n+1, suppose airline X does not offer an odd round trip. We claim that we can divide the cities into two sets A and B, such that X does not fly between any two cities in A, and X does not fly between any two cities in B. For start by putting any city C into A, then put into B all the cities to which X flies direct from a city in A. Then put into A all the cities to which X flies direct from a city in B. Repeat until we stop adding cities. If this does not exhaust the cities, then put one of the remaining cities into A and repeat, and so on.
Now at least one of A, B must have > 2n cities. Also it must be served entirely by the remaining n airlines. So the result follows by induction.
Since 1983 > 210, the required result follows.
© John Scholes
jscholes@kalva.demon.co.uk
26 Nov 2003
Last corrected/updated 26 Nov 03