# Can we find two numbers from $n+2$ numbers chosen from $\{1,2,3,\cdots\}$?

Let $n\ge 2$ is given and choose $n+2$ integers from the set $\{1,2,3,\cdots,3n\}$ then can we find two numbers whose difference is greater than $n$ but less than $2n$?

I try to prove it by using pigeon principle. I partitioned $\{1,2,3,\cdots,3n\}$ from the sets $$\{\{k,2n-1+k\}:1\le k\le n+1\}\cup \{\{k\} :n+2\le k\le 2n-1\}.$$ However I don't know how to proceed it. Thanks for any help. (It is homework problem so I don't want a full solution, but a hint or idea.)

• From your set-up, it looks like you have $(n+1)+(n-2)$ sets. This is too many for the pigeonhole principle in this case. – Michael Burr Mar 31 '15 at 12:01
• @MichaelBurr I know it, but if $n+2$ numbers are chosen and no numbers contained from same $\{k,2n-1+k\}$ then at least one number lies between $n+2$ and $2n-1$ and I try to use it. – Hanul Jeon Mar 31 '15 at 12:04
• The pigeon hole principle is a good place to start. Try the sets $\{1,\dots,n\}$, $\{n+1,\dots,2n\}$, $\{2n+1,\dots,3n\}$; it should also help to distinguish the case where the middle set contains one of the chosen numbers from the one where it doesn't. – Klaus Draeger Mar 31 '15 at 12:11

Consider a set of $n+1$ numbers. The first number in the list removes $n-1$ candidates - i.e. choosing any one of these results in a success. Every other choice from the list removes at least one more candidate, and there are $n$ of them. So we have the $n+1$ chosens and $n-1+n$ removals, $=3n$ in total, so there is nowhere left to go.
Let $S$ your set of $n+2$ numbers. If $S \cap \{n+1,\ldots,2n\} \neq \emptyset$, then you're done (why?). Otherwise the intersection is empty, and since we have $n+2$ integers then $A=S\cap \{1,\ldots,n\}\neq \emptyset$ and $B=S\cap \{2n+1,\ldots,3n\}\neq \emptyset$. Choose $a \in A$ and $b \in B$. Then $b-a>n$. But such difference cannot be so large..