# Math Help - Combinatorics

1. ## Combinatorics

Suppose you are given a set of 100 distinct positive integers. Show that there exist four intergers {a,b,c,d,} in this set such that a-b+c-d|2009.

Sixteen distinct integers are choosen between 1 and 30 inclusive. Show that you can always find a pair of integers(among these 16) such that their difference is 3.

2. Originally Posted by Juancd08
Suppose you are given a set of 100 distinct positive integers. Show that there exist four integers {a,b,c,d,} in this set such that a-b+c-d|2009.
There must be some extra condition on the size of the integers in the set. Otherwise, you could have the numbers $10^{n+5}\quad(1\leqslant n\leqslant100)$. In any set of four of those numbers, the largest one would swamp the sum or difference of the other three. So a–b+c–d would be much larger than 2009, and could not be a factor of it.

Originally Posted by Juancd08
Sixteen distinct integers are chosen between 1 and 30 inclusive. Show that you can always find a pair of integers(among these 16) such that their difference is 3.
If you want to avoid pairs that differ by 3, then in the set 1,4,7,10,13,16,19,22,25,28 you could not pick any two consecutive elements. So the maximum number chosen from this set would be 5. Similarly for the sets 2,5,8,...,29 and 3,6,9,...,30, giving a total of at most 15 numbers altogether.