Pigeonhole principle?

Printable View

October 16th 2008, 08:50 AM
alexmahone

Pigeonhole 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.
October 16th 2008, 09:34 AM
ThePerfectHacker

Quote:

Originally Posted by alexmahone

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.

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 $\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 $a_1 < a_2 < a_3 < a_4 < a_5 < a_6$ . Since these guys have the same remainder is means $a_{i+1}-a_i$ is a multiple of three. Assume (for contradiction) that each $a_{i+1} - a_i \not = 3$ then it would mean $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 $a_6 - a_1 \geq (5)(24) = 120$ . This is a contradiction therefore there must be $i$ so that $a_{i+1} - a_i = 3$ .
October 16th 2008, 10:08 AM
alexmahone

Quote:

Originally Posted by ThePerfectHacker

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 $\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 $a_1 < a_2 < a_3 < a_4 < a_5 < a_6$ . Since these guys have the same remainder is means $a_{i+1}-a_i$ is a multiple of three. Assume (for contradiction) that each $a_{i+1} - a_i \not = 3$ then it would mean $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 $a_6 - a_1 \geq (5)(24) = 120$ . This is a contradiction therefore there must be $i$ so that $a_{i+1} - a_i = 3$ .

Thanks so much for the prompt reply! :)