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 elements of A should differ by 3.

Printable View

- Oct 16th 2008, 08:50 AMalexmahonePigeonhole principle?
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 elements of A should differ by 3.

- Oct 16th 2008, 09:34 AMThePerfectHacker
Let the pigeons be the 16 numbers that you choose. And let the holes be either 0 or 1 or 2, a number is determined in which hole it goes to by its remainder upon division by 3 (i.e. 17 goes into the 2 hole). This means that there are at least $\displaystyle \left\lceil {16/3}\right\rceil = 6$ elements in A that all have the same remainder upon division by three. Let us call these elements $\displaystyle a_1 < a_2 < a_3 < a_4 < a_5 < a_6$. Since these guys have the same remainder is means $\displaystyle a_{i+1}-a_i$ is a multiple of three. Assume (for contradiction) that each $\displaystyle a_{i+1} - a_i \not = 3$ then it would mean $\displaystyle a_{i+1} - a_i \geq 24$ because it needs to be a multiple of three and one of 6,9,12,15,18 or 21 are allowed. But then this means $\displaystyle a_6 - a_1 \geq (5)(24) = 120$. This is a contradiction therefore there must be $\displaystyle i$ so that $\displaystyle a_{i+1} - a_i = 3$.

- Oct 16th 2008, 10:08 AMalexmahone