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.)

  • $\begingroup$ 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. $\endgroup$ – Michael Burr Mar 31 '15 at 12:01
  • $\begingroup$ @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. $\endgroup$ – Hanul Jeon Mar 31 '15 at 12:04
  • 2
    $\begingroup$ 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. $\endgroup$ – 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..


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.