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 '15 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 '15 at 6:12
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 '15 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 '15 at 6:31
  • $\begingroup$ You are welcome. $\endgroup$ Jul 10 '15 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$
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.