Prove that two elements of $A$ should differ by 3. Let $A$ consist of $16$ elements of the set $\{1,2,3,...,106\}$ so that no two element differ by $6,9,12,15,18$ or $21$. Prove that two elements of $A$ should differ by 3.
 A: Let us separate the set $U=\{1,2,\cdots,106\}$ into $5$ 'rooms' as
$$\{1,2,\cdots,22\},\{23,24,\cdots,44\},\{45,46,\cdots,66\},\{67,68,\cdots,88\},\{89,90,\cdots,106\}$$
Note that each of the first four rooms has $22$ elements and that the last room has $18$ elements.
Now, since we choose $16$ elements from the set $U$, at least some $4$ elements have to be chosen from either one of the five rooms.
We may suppose that we choose $4$ elements from the set $\{1,2,\cdots,22\}$. Considering in mod $3$, we have to choose some $2$ elements which are congruent in mod $3$. The difference between the two elements is $3$. Q.E.D.
A: Assume $A$ has no two points differing by $3$. Let $C = \{0,3,6,9,12,15,18,21\}$.
Consider the sets of the form $i + 24j + C$ for $i=1,2,3$, and $j=0,\dots,4$. There are $15$ of them. They are disjoint. Their union is $\{1,2,\dots,120\}$. And each one can contain at most one element from $A$.
This proof shows that $A$ can be allowed to contain elements up to $120$, not just $106$.
