# Pigeon-hole Principle

• Aug 5th 2011, 02:48 AM
alexmahone
Pigeon-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 AM
Also sprach Zarathustra
Re: Pigeon-hole Principle
Quote:

Originally Posted by alexmahone
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 $[1,3n]$ as $3n-a$, a can be $0$.

Second, we add $a$ to our all chosen numbers, that would not change the result:

Say, if $x_i$ and $x_j$ are chosen ones, $x_i-x_j=t$; then by adding to $x_i$ and $x_j$ $a$ we will still get $(x_i+a)-(x_j+a)=t$.

So by adding a to the largest chosen, $3n-a$, we will get $3n$.

Now, we have two cases, one is if one of $n+1$ other chosen numbers is from $[n+1,2n-1]$,

if so, we are done, if $x_k\in [n+1,2n-1]$, then $n<3n-x_k<2n$.

The second case is if the other n+1 chosen numbers are from $[1,n]$ and $[2n,3n-1]$.

Now, consider the following $n$ pairs:

$(1,2n), (2,2n+1),...,(i,i+2n-1),...,(n,3n-1)$

(If $(x,y)$ is a asome above pair then $x$ is from $[1,n]$ and $y$ is from $[2n,3n-1]$)

So, we have $n$ pairs, but we choose $n+1$ numbers, then there must to be one pair with two chosen elements.

Say, that is $(k,k+2n-1)$, $x=k$, $y=k+2n-1$,

$n
• Aug 5th 2011, 05:53 AM
alexmahone
Re: 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 AM
Also sprach Zarathustra
Re: Pigeon-hole Principle
Quote:

Originally Posted by alexmahone
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"?

The pair (1,2n) is ordered set that contains two elements, one from [1,n] and one from [2n,3n-1].

(1,2n) - 1 is from closed interval [1,n] ; 2n is from closed interval [2n,3n-1].
• Aug 5th 2011, 06:06 AM
alexmahone
Re: Pigeon-hole Principle
Quote:

Originally Posted by Also sprach Zarathustra
The pair (1,2n) is ordered set that contains two elements, one from [1,n] and one from [2n,3n-1].

(1,2n) - 1 is from closed interval [1,n] ; 2 is from closed interval [2n,3n-1].

But I thought you added "a" to all the numbers in the second step. So shouldn't we have (1+a, 2n+a) etc?
• Aug 5th 2011, 06:20 AM
Also sprach Zarathustra
Re: Pigeon-hole Principle
Quote:

Originally Posted by alexmahone
But I thought you added "a" to all the numbers in the second step. So shouldn't we have (1+a, 2n+a) etc?

Okay!

The adding a needed only at the first stage, the purpose was eliminate closed interval [n+1,2n-1].