Welcome to NRICH.

 
Proof by contradiction
By Maria Jose Leon-Sotelo Esteban (T3819) on Friday, January 12, 2001 - 07:23 am:

Let A consist of 16 elements of the set {1,2,3,...,106},so that no two elements of A differ by 6,9,12,15,18, or 21. Prove that two of the elements of A must differ by 3.

Maria Jose

By Michael Doré (Md285) on Friday, January 12, 2001 - 08:25 am:

For a contradiction let's suppose there exists a set A of 16 elements which is a subset of {1,2,3,...,106} and no two elements of A differ by 3,6,9,12,15,18 or 21.

Define sets P,Q,R by:

P = {i in A such that i = 0 (mod 3)}
Q = {i in A such that i = 1 (mod 3)}
R = {i in A such that i = 2 (mod 3)}

so that each of the 16 members of A is in exactly one of P,Q,R.

If P,Q,R all have fewer than 6 elements (i.e. <=5) then together they only have at most 15 elements, which would be a contradiction as A has 16 elements. So one of P,Q,R must have at least 6 elements. Each of the 6 elements differ by a multiple of 3, excluding 3,6,9,12,15,18,21 so the difference between each element is at least 24. Therefore A must contain 6 elements each of which differ by 24 or more. This means the highest and lowest element differ by at least 24×5 = 120 which is a contradiction as A is just {1,2,3,...,106}.

Therefore the set described in your message must have two elements which differ by 3.