Let S consist of 16 elements of the set (1,2,3, ... , 106) so
that no two elements of S differ by 6; 9; 12; 15; 18; or 21.

Prove that at least two of
the elements of S must differ by 3.

(In reply to

analytic solution by Paul)

Very nicely done, Paul. In fact, you have proved a stronger statement, namely that this is true if 16 elements were picked from (1,2,3,...,120). I wonder why the puzzle author used a smaller set.