IMO 2003 · Problem 1

\(S\) is the set \(\{1,2,3,\ldots,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 \(\{a+x_i\mid a\in A\}\) are all pairwise disjoint.

Official text of the problem. Official problem paper (PDF)

Solution

Write \(A+x=\{a+x\mid a\in A\}\), and let \[ D=\{a-b\mid a,b\in A\}. \] There are \(101\cdot100\) ordered pairs of distinct elements of \(A\), while every pair with equal elements gives the difference \(0\). Consequently, \[ |D|\le 101\cdot100+1=10101. \]

We choose the shifts successively. Suppose that \(0\le k\le99\) shifts \(x_1,\ldots,x_k\) have already been chosen so that their translates are pairwise disjoint.

If a candidate \(x\in S\) satisfies \[ (A+x)\cap(A+x_i)\ne\varnothing, \] then \(a+x=b+x_i\) for some \(a,b\in A\), so \[ x=x_i+(b-a)\in x_i+D. \] Thus all candidates that could intersect an existing translate belong to \[ \bigcup_{i=1}^{k}(x_i+D), \] which contains at most \[ k|D|\le99\cdot10101=999999 \] integers. Since \(S\) contains \(1000000\) integers, we can choose \(x_{k+1}\in S\) outside this union. Its translate is disjoint from every previously chosen translate. Moreover, \(0\in D\), so this choice also ensures \(x_{k+1}\ne x_i\) for every \(i\le k\).

Starting with \(k=0\) and repeating this step produces the required \(100\) distinct shifts. \(\square\)

The solution was checked against Evan Chen's published IMO solution notes.