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.

Printable View

- Aug 5th 2011, 02:48 AMalexmahonePigeon-hole Principle
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.

- Aug 5th 2011, 05:37 AMAlso sprach ZarathustraRe: Pigeon-hole Principle
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$ - Aug 5th 2011, 05:53 AMalexmahoneRe: Pigeon-hole Principle
How come "a" doesn't figure in the rest of the solution?

For example, how do you consider the pair (1, 2n)? Shouldn't the smallest number of the set now be "a"? - Aug 5th 2011, 06:03 AMAlso sprach ZarathustraRe: Pigeon-hole Principle
- Aug 5th 2011, 06:06 AMalexmahoneRe: Pigeon-hole Principle
- Aug 5th 2011, 06:20 AMAlso sprach ZarathustraRe: Pigeon-hole Principle