IMO 1978/B3 solution

IMO 1978

Problem B3

An international society has its members from six different countries. The list of members has 1978 names, numbered 1, 2, ... , 1978. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice the number of a member from his own country.

Solution

The trick is to use differences.

At least 6.329 = 1974, so at least 330 members come from the same country, call it C1. Let their numbers be a₁ < a₂ < ... < a₃₃₀. Now take the 329 differences a₂ - a₁, a₃ - a₁, ... , a₃₃₀ - a₁. If any of them are in C1, then we are home, so suppose they are all in the other five countries.

At least 66 must come from the same country, call it C2. Write the 66 as b₁ < b₂ < ... < b₆₆. Now form the 65 differences b₂ - b₁, b₃ - b₁, ... , b₆₆ - b₁. If any of them are in C2, then we are home. But each difference equals the difference of two of the original a_is, so if it is in C1 we are also home.

So suppose they are all in the other four countries. At least 17 must come from the same country, call it C3. Write the 17 as c₁ < c₂ < ... < c₁₇. Now form the 16 differences c₂ - c₁, c₃ - c₁, ... , c₁₇ - c₁. If any of them are in C3, we are home. Each difference equals the difference of two b_is, so if any of them are in C2 we are home. [For example, consider c_i - c₁. Suppose c_i = b_n - b₁ and c₁ = b_m - b₁, then c_i - c₁ = b_n - b_m, as claimed.]. Each difference also equals the difference of two a_is, so if any of them are in C1, we are also home. [For example, consider c_i - c₁, as before. Suppose b_n = a_j - a₁, b_m = a_k - a₁, then c_i - c₁ = b_n - b_m = a_j - a_k, as claimed.]

So suppose they are all in the other three countries. At least 6 must come from the same country, call it C4. We look at the 5 differences and conclude in the same way that at least 3 must come from C5. Now the 2 differences must both be in C6 and their difference must be in one of the C1, ... , C6 giving us the required sum.

Solutions are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

20th IMO 1978