IMO 1978 SL 10

Origin: NET

Problem

An international society has its members in 6 different countries. The list of members contains 1978 names, numbered 1, 2, . . . ,

Solution

Assume the opposite. One of the countries, say A, contains at least 330 members a1, a2, . . . , a330 of the society ( 6 \cdot 329 = 1974). Consider the differences a330 −ai, = 1, 2, . . . , 329: the members with these numbers are not in A, so at least 66 of them, a330 −ai1, . . . , a330 −ai66, belong to the same country, say B. Then the differences (ai66 −a330) −(aij −a330) = ai66 −aij, j = 1, 2, . . . , 65, are neither in A nor in B. Continuing this procedure, we find that 17 of these differences are in the same country, say C, then 6 among 16 differences of themselves in a country D, and 3 among 5 differences of themselves in E; finally, one among two differences of these 3 differences belong to country F, so that the difference of themselves cannot be in any country. This is a contradiction. Remark. The following stronger ([6!e] = 1957) statement can be proved in the same way. Schurr’s lemma. If n is a natural number and e the logarithm base, then for every partition of the set {1, 2, . . ., [en!]} into n subsets one of these subsets contains some two elements and their difference.