IMO 2003 SL C1

Origin: BRA | Category: Combinatorics

Problem

Let A be a 101-element subset of the set S = {1, 2, . . . , 1000000}. Prove that there exist numbers t1, t2, . . . , t100 in S such that the sets Aj = {x + tj | x \inA}, j = 1, 2, . . . , 100, are pairwise disjoint.

Solution

Consider the set D = {x−y | x, y \inA}. Obviously, the number of elements of the set D is less than or equal to 101\cdot100+1. The sets A+ti and A+tj

are disjoint if and only if ti −tj ̸\inD. Now we shall choose inductively 100 elements t1, . . . , t100. Let t1 be any element of the set S \ D (such an element exists, since the number of elements of S is greater than the number of elements of D). Suppose now that we have chosen k (k \leq99) elements t1, . . . , tk from D such that the difference of any two of the chosen elements does not belong to D. We can select tk+1 to be an element of S that does not belong to any of the sets t1 +D, t2 +D, . . . , tk +D (this is possible to do, since each of the previous sets has at most 101 \cdot 100 + 1 elements; hence their union has at most 99(101 \cdot 100 + 1) = 999999 < 1000000 elements).