Problem 1

Let

A

be a 101-element subset of

S=\{1,2,\ldots,10^6\}

. Prove that there exist numbers

t_1,t_2,\ldots,t_{100}

S

such that the sets

A_j=\{x+t_j\mid x\in A\}

j=1,2,\ldots,100

, are pairwise disjoint.

Step 2 of 3: Count blocked candidates

Previous step Next step

In plain words

Count blocked candidates

10^6\le |T|(101\cdot100+1)

Detailed analysis

For a maximal admissible set $T$ , every candidate in $S$ is either already in $T$ or equals $t_i+b-a$ for some $t_i\in T$ and distinct $a,b\in A$ . Hence the displayed bound.