# Pigeonhole principle: prove that any set of $n+1$ integers from $\{1,2,…,2n\}$ has two consecutive integers differ by one.

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?

• What does it mean by "regard each entry in $T_0$ and $T_1$ as a box containing some integers" please? – PSPACEhard Apr 26 '17 at 8:51
• 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 – whatever Apr 26 '17 at 8:53
• So how "box" is defined here? – PSPACEhard Apr 26 '17 at 8:53
• Sets are unordered, so "consecutive" technically doesn't make sense. – Henrik Apr 26 '17 at 8:54

## 1 Answer

Hint:

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

• I still don't understand. Can you explain a bit further? – whatever Apr 26 '17 at 9:00
• @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$. – PSPACEhard Apr 26 '17 at 9:02
• what if the holes are $\{2,4\},\{8,6\}, ... \{2n-3,2n\}$? In this case they wouldn't differ by 1 – whatever Apr 26 '17 at 9:07
• @whatever Why do you define holes in this way? – PSPACEhard Apr 26 '17 at 9:08
• 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? – whatever Apr 26 '17 at 9:33