IMO 1983 SL 1

Origin: AUS

Problem

The localities P1, P2, . . . , P1983 are served by ten international airlines A1, A2, . . . , A10. It is noticed that there is direct service (without stops) between any two of these localities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.

Solution

Suppose that there are n airlines A1, . . . , An and N > 2n cities. We shall prove that there is a round trip by at least one Ai containing an odd number of stops. For n = 1 the statement is trivial, since one airline serves at least 3 cities and hence P1P2P3P1 is a round trip with 3 landings. We use induction on n, and assume that n > 1. Suppose the contrary, that all round trips by An consist of an even number of stops. Then we can separate the cities into two nonempty classes Q = {Q1, . . . , Qr} and R = {R1, . . . , Rs} (where r+s = N), so that each flight by An runs between a Q-city and an R-city. (Indeed, take any city Q1 served by An; include each city linked to Q1 by An in R, then include in Q each city linked by An to any R-city, etc. Since all round trips are even, no contradiction can arise.) At least one of r, s is larger than 2n−1, say r > 2n−1. But, only A1, . . . , An−1 run between cities in {Q1, . . . , Qr}; hence by the induction hypothesis at least one of them flies a round trip with an odd number of landings, a contradiction. It only remains to notice that for n = 10, 2n = 1024 < 1983. Remark. If there are N = 2n cities, there is a schedule with n airlines that contain no odd round trip by any of the airlines. Let the cities be Pk, k = 0, . . . , 2n −1, and write k in the binary system as an n-digit number a1 . . . an (e.g., 1 = (0 . . . 001)2). Link Pk and Pl by Ai if the ith digits k and l are distinct but the first i −1 digits are the same. All round trips under Ai are even, since the ith digit alternates.