We chose n + 2 numbers from the set 1, 2, ..., 3n. Prove that there are always two among the chosen numbers whose difference is more than n but less than 2n.
The solution is from the net, in "my words",http://www.worldscibooks.com/etextbo...177_chap01.pdf
page: 16, #11
First, denote the largest chosen number from as , a can be .
Second, we add to our all chosen numbers, that would not change the result:
Say, if and are chosen ones, ; then by adding to and we will still get .
So by adding a to the largest chosen, , we will get .
Now, we have two cases, one is if one of other chosen numbers is from ,
if so, we are done, if , then .
The second case is if the other n+1 chosen numbers are from and .
Now, consider the following pairs:
(If is a asome above pair then is from and is from )
So, we have pairs, but we choose numbers, then there must to be one pair with two chosen elements.
Say, that is , , ,