how to apply hint to question involving the pigeonhole principle 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.
 A: 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.
A: Here is $9$ done explicitly:  Break the set into subsets with a difference of $9$: $\{1,10,19,28,\ldots,100\},\{2,11,20,\ldots 92\},\ldots \{9,18,27,\ldots 99\}$.  Note that there is one subset with $12$ members and eight with $11$ members.  If you want to avoid a pair with a difference of $9$ among your $55$ numbers, you can't pick a pair of neighbors from any set.  That means you can only pick six from within each set, but that gives you only $54$ numbers, so with $55$ you will have a pair with difference $9$.
The reason this fails with $11$ is you get one subset with $10$ members and ten with $9$ members.  You can pick $5$ out of each and avoid neighbors.
