IMO 2003

S is the set {1, 2, 3, ... , 1000000}. Show that for any subset A of S with 101 elements we can find 100 distinct elements x_i of S, such that the sets x_i + A are all pairwise disjoint. [Note that x_i + A is the set {a + x_i | a is in A} ].

Solution

Thanks to Li Yi

Having found x₁, x₂, ... , x_k there are k·101·100 forbidden values for x_k+1 of the form x_i + a_m - a_n with m and n unequal and another k forbidden values with m = n. Since 99·101·100 + 99 = 10⁶ - 1, we can successively choose 100 distinct x_i.

Gerhard Woeginger sent me a similar solution

44th IMO 2003

© John Scholes
jscholes@kalva.demon.co.uk
24 Jul 2003
Last corrected/updated 24 Jul 2003