Let $n \ge 1$ be an integer. Use the Pigeonhole Principle to prove that in any set of $n + 1$ integers from $\{1, 2, . . . , 2n\}$, there are two integers differ by one.
I've attempt and come up with this: Let S be $\{1,2,...,2n\}$, $T_0$ be a subset of S with $n$ elements, $T_1$ is a subset of S with $n+1$ elements. We form $T_1$ by adding a number to $T_0$. If $T_0$ already has two integers differ by one, then we're done. If $T_0$ has no integers differ by one, how do we know $T_1$, having 1 more number, has two integers differ by one?

  • $\begingroup$ What does it mean by "regard each entry in $T_0$ and $T_1$ as a box containing some integers" please? $\endgroup$ – PSPACEhard Apr 26 '17 at 8:51
  • $\begingroup$ I mean that each box in $T_0$ contains exactly 1 integer. $T_1$ is formed by adding one number to $T_0$, then one of the boxes in $T_1$ must have 2 integers $\endgroup$ – whatever Apr 26 '17 at 8:53
  • $\begingroup$ So how "box" is defined here? $\endgroup$ – PSPACEhard Apr 26 '17 at 8:53
  • $\begingroup$ Sets are unordered, so "consecutive" technically doesn't make sense. $\endgroup$ – Henrik Apr 26 '17 at 8:54


There are $n$ holes in $\{1, 2, \cdots, 2n\}$, namely, $\{1, 2\}$, $\{3, 4\}$, $\cdots$, $\{2n - 1, 2n\}$.

  • $\begingroup$ I still don't understand. Can you explain a bit further? $\endgroup$ – whatever Apr 26 '17 at 9:00
  • $\begingroup$ @whatever By pigeonhole principle, there must be two numbers belonging to the same hole. Note that the numbers in the same hole differ by $1$. $\endgroup$ – PSPACEhard Apr 26 '17 at 9:02
  • $\begingroup$ what if the holes are $\{2,4\},\{8,6\}, ... \{2n-3,2n\}$? In this case they wouldn't differ by 1 $\endgroup$ – whatever Apr 26 '17 at 9:07
  • $\begingroup$ @whatever Why do you define holes in this way? $\endgroup$ – PSPACEhard Apr 26 '17 at 9:08
  • $\begingroup$ Ok I got it. After picking $n$ numbers from $n$ holes, each hole remains $1$ number. If I pick one of those numbers, since numbers belonging to the same hole differs by one, the $n+1$ elements set would have $2$ numbers differ by one. Is that right? $\endgroup$ – whatever Apr 26 '17 at 9:33

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.