The following question is from cut-the-knot.org's page on the pigeonhole principle
Question
Prove that however one selects 55 integers $1 \le x_1 < x_2 < x_3 < … < x_{55} \le 100$, there will be some two that differ by 9, some two that differ by 10, a pair that differ by 12, and a pair that differ by 13. Surprisingly, there need not be a pair of numbers that differ by 11.
The Hint
Given a run of $2n$ consecutive integers: $a + 1, a + 2, …, a + 2n – 1, a + 2n$, there are n pairs of numbers that differ by n: $(a+1, a+n+1), (a + 2, a + n + 2), \dots, (a + n, a + 2n)$. Therefore, by the Pigeonhole Principle, if one selects more than n numbers from the set, two are liable to belong to the same pair that differ by $n$.
I understood the hint but no concrete idea as to how to apply it, but here are my current insights:
My Insights
break the set of 100 possible choices into m number of 2n(where $n \in \{9,12,13\}$ ) consecutive numbers and since 55 numbers are to be chosen , show that even if one choses randomly there will be n+1 in one of the m partitions and if so, by the hint there will exist a pair of two numbers that differ by n.
Best Answer
The easiest example is to do $10$. Then break up your set into $5$ sets, $$\{1,\dots,20\}\\\{21,\dots 40\}\\\vdots\\\{81,\dots,100\}$$
Since you have selected $55$ elements, you must have selected $11$ elements from one of these partitions. Then from the hint, you are done.
The case for $10$ is easy because $20$ divides $100$. The case of $12$ is harder. Partition the numbers as:
$$\{1,\dots,24\}\\\{25,\dots,48\}\\\{49,\dots,72\}\\\{73,\dots, 96\}\\\{97,98,99,100\}$$
Now we know that we've selected at least $51=55-4$ from the first four sets, and hence at least $13$ from one of them, and again we are done by the hint.
The problem for $11$ is that the "remainder" is large. When we partition $100$ into sets of $22$, we are left with $12$ elements. That's a large enough number of elements left to "break" the logic above - we can pick up to $11$ different elements from that remainder, and we have $44$ to parcel out amongst the first four partitions, which we can do by putting $11$ in each partition. It is not hard to find a counter-example for $11$ precisely this way.
More generally, given $N$ and $k$, let $m=k\left\lfloor \frac{N}{2k}\right\rfloor$. Then you can select from $\{1,\dots,N\}$ the following number of elements:$$m + \min(k,N-2m)$$ and not get a pair that differ by $k$. But it you try to select more than that number, you must get a pair with difference $k$.
In the case $N=100$ and $k=11$, $m=44$ and $\min(k,N-2m)=11$ so we can select $55$ such numbers.