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 $\displaystyle [1,3n]$ as $\displaystyle 3n-a$, a can be $\displaystyle 0$.
Second, we add $\displaystyle a$ to our all chosen numbers, that would not change the result:
Say, if $\displaystyle x_i$ and $\displaystyle x_j$ are chosen ones, $\displaystyle x_i-x_j=t$; then by adding to $\displaystyle x_i$ and $\displaystyle x_j$ $\displaystyle a$ we will still get $\displaystyle (x_i+a)-(x_j+a)=t$.
So by adding a to the largest chosen, $\displaystyle 3n-a$, we will get $\displaystyle 3n$.
Now, we have two cases, one is if one of $\displaystyle n+1$ other chosen numbers is from $\displaystyle [n+1,2n-1]$,
if so, we are done, if $\displaystyle x_k\in [n+1,2n-1]$, then $\displaystyle n<3n-x_k<2n$.
The second case is if the other n+1 chosen numbers are from $\displaystyle [1,n]$ and $\displaystyle [2n,3n-1]$.
Now, consider the following $\displaystyle n$ pairs:
$\displaystyle (1,2n), (2,2n+1),...,(i,i+2n-1),...,(n,3n-1)$
(If $\displaystyle (x,y)$ is a asome above pair then $\displaystyle x$ is from $\displaystyle [1,n]$ and $\displaystyle y$ is from $\displaystyle [2n,3n-1]$)
So, we have $\displaystyle n$ pairs, but we choose $\displaystyle n+1$ numbers, then there must to be one pair with two chosen elements.
Say, that is $\displaystyle (k,k+2n-1)$, $\displaystyle x=k$, $\displaystyle y=k+2n-1$,
$\displaystyle n<y-x=k+2n-1-k=2n-1<2n$