MathLabs

Problem 1

Let AA be a 101-element subset of S={1,2,…,106}S=\{1,2,\ldots,10^6\}. Prove that there exist numbers t1,t2,…,t100t_1,t_2,\ldots,t_{100} in SS such that the sets Aj={x+tj∣x∈A}A_j=\{x+t_j\mid x\in A\}, j=1,2,…,100j=1,2,\ldots,100, are pairwise disjoint.
Step 1 of 3: Characterize a collision
Previous stepNext step
In plain words

Characterize a collision

t=ti+b−at=t_i+b-a
Detailed analysis

Two translates intersect only if t−ti=a−bt-t_i=a-b for distinct a,b∈Aa,b\in A. Thus a new shift is forbidden only by a value ti+b−at_i+b-a.