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

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

- October 16th 2008, 10: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 elements in A that all have the same remainder upon division by three. Let us call these elements . Since these guys have the same remainder is means is a multiple of three. Assume (for contradiction) that each then it would mean 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 . This is a contradiction therefore there must be so that .

- October 16th 2008, 11:08 AMalexmahone