6
$\begingroup$

Considering n=5 i have $\{1,2,3,...,10\}$ .Making pairs such as $\{1,2\}$ ,$\{2,3\}$ ... total of $9$ pairs which are my holes and $6$ numbers are to be choosen which are pigeons .So one hole must have two pigeons ,i am done .Is this correct ?

In general if we have $2n$ numbers and then we have $2n-1$ holes and $n+1$ pigeons ,But for $n=3$ onwards it is valid ? There is something wrong i think

Thanks

$\endgroup$
2
  • $\begingroup$ Question edited $\endgroup$
    – Taylor Ted
    Jul 10, 2015 at 6:11
  • $\begingroup$ If we need to choose $n$ elements from $\{1,2,\cdots, mn\}$ the minimum distance will be $\dfrac{mn}n= m$ If $n+1$ elements are to be chosen, one distance has to be $m-1$ $\endgroup$ Jul 10, 2015 at 6:12

8 Answers 8

9
$\begingroup$

Suppose that you can select $n+1$ distinct integers from $\{1,\ldots,2n\}$ in such a way that all pairs differ by at least $2$. Let the chosen integers be denoted as $x_1,\ldots, x_{n+1}$. Also, let them be arranged in increasing order. Then, one has \begin{align*} x_1\geq&\,1,\\ x_2\geq&\,x_1+2\geq 3,\\ x_3\geq&\,x_2+2\geq 5,\\ \vdots&\\ x_k\geq&\,2k-1,\\ \vdots&\\ x_{n+1}\geq&\,2(n+1)-1=2n+1>2n. \end{align*} This is a contradiction, since $x_{n+1}$ is supposed to be at most $2n$.

$\endgroup$
5
$\begingroup$

Well, in your case when $n=5$, you shouldn't make the pairs $\lbrace1,2\rbrace,\lbrace2,3\rbrace,...,\lbrace8,9\rbrace,\lbrace9,10\rbrace$, but rather $\lbrace1,2\rbrace,\lbrace3,4\rbrace,...,\lbrace7,8\rbrace,\lbrace9,10\rbrace$, as in the first case the same integer appears in two different pairs.

When we have the correct pairs established, we can directly apply the pigeonhole principle on our $n=5$ "holes" $\lbrace1,2\rbrace,\lbrace3,4\rbrace,...,\lbrace7,8\rbrace,\lbrace9,10\rbrace$, and we see that if we have $n+1=6$ "pigeons" in the "holes", at least one of our "holes" must contain two pigeons.

We then apply the same reasoning to the general case.

$\endgroup$
1
  • $\begingroup$ Oh i made a blunder ! Thanks ... $\endgroup$
    – Taylor Ted
    Jul 10, 2015 at 6:27
4
$\begingroup$

You have nine holes and six pigeons, so the pigeonhole principle doesn't help because $6<9$.
Just use five holes $\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{9,10\}$

$\endgroup$
2
$\begingroup$

Suppose to the contrary that there are no two consecutive numbers among the $n+1$ chosen numbers. Then there are $n$ "gaps" between the chosen numbers, with at least $1$ non-chosen number in each gap. But that would mean the total number of numbers is $\ge (n+1)+n$. This is impossible, since we only have $2n$ numbers.

$\endgroup$
2
  • $\begingroup$ Thats a very good approach .Thanks $\endgroup$
    – Taylor Ted
    Jul 10, 2015 at 6:31
  • $\begingroup$ You are welcome. $\endgroup$ Jul 10, 2015 at 6:42
2
$\begingroup$

Suppose not, then numbers differ by at least two. Order the numbers $a_1<a_2<\dots <a_n$. Then $a_1\geq 1$. We prove $a_i\geq 1+(i-1)2$ by induction

Base step $i=1$ is clear (we have to prove $a_1\geq 1+(1-1)2+1=1$)

Inductive step. We have $a_{i}\geq 1+(i-1)2$ and $a_{i+1}\geq a_i+2$ so $a_{i+1}\geq 1+(i-1)2+2=1+((i+1)-1)2$. Taking $i=n+1$ we get $a_n\geq 1+(n+1)2=2n+1$, a contradiction since all number must be in set $\{1,2,3\dots 2n\}$

$\endgroup$
0
1
$\begingroup$

Why should there be a problem from n = 3 onwards ?

Remember there are to be 2n numbers, n pairs.

In your example, the pairs you made should be 5 pairs, {1,2}, {3,4}, ... {9,10}

We can choose max 1 # from each pair, so all the pigeon holes have been "used up" by the $n_{th}$ draw

$\endgroup$
1
$\begingroup$

Given the set $S=\{1,2,3,\ldots,2n\}$.We have to choose $n+1$ points from $S$,and there must be $2$ of them which are consecutive.

To apply the Pigeon-hole Principle here, clearly, there are $n+1$ "letters" so that the number of Pigeon-holes or "letter-boxes" must be $n$.

So, given $n$ boxes, there must be at least two integers amongst the $n+1$ integers which share the property that they are consecutive.

Why $n+1$ integers?What if we take $\gt n+1$ or $\lt n+1$ integers from $S$?

If we take $\gt n+1$ integers from $S$ since the conclusion holds for $n+1$, the extra numbers can be thrown for free, and the result holds good.

If we take $\lt n+1$ integers from $ S$, say for example $ n$, the result doesn't hold,

A simple choice for this is the set $\{1,3,5,\ldots,2n-1\}$ or the set $\{2,4,6,\ldots,2n\}$ where there are no consecutive integers.

$\endgroup$
1
$\begingroup$

You have to choose $n+1$ integers from the set $S$ = {1, 2, 3, . . ., 2n}.

if you construct the pigeonholes as follows: {$1,2$} {$3,4$} {$5,6$} . . . { $2n-1$ , $2n$ }

we can notice that there are $n$ possible pairs, by PHP $n+1 > 1 *n$ thus there exists at least 2 integers that belong to the same pigeonhole, consequently, those two integer differ by 1.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .