Prove that however one selects $55$ integers $1 ≤ x_1 < x_2 < x_3 < ... < x_{55} ≤ 100$, there will be some two that differ by 9, 10, 12 and 13.

Question

Prove that however one selects $55$ integers $1 ≤ x_1 < x_2 < x_3 < ... < x_{55} ≤ 100$, there will be some two that differ by 9, 10, 12 and 13.

This was to be done with Pigeonhole Principle. I solved the one which asked to show that there existed two numbers with a common difference of 10. How do I show the other cases when the difference is 9, 12 or 13?

My Proof:

Consider the ranges $[1, 20], [21, 40], [41, 60], [61, 80], [81, 100]$. There are 5 ranges and 55 numbers, so atleast one range must contain 11 numbers by the Pigeonhole Principle. Let that range be $[a, a+19]$.

Now, consider the set of sets

$$S = \{\{a, a+10\}, \{a+1, a+11\}, \cdots , \{a+9, a+19\} \}$$

Because $|S| = 10$ and there are 11 numbers, two numbers must fall in the same smaller set by the Pigeonhole Principle. Q. E. D.

So, how can I prove this for the other cases.

Answer 1

For $9$. Consider the classes $\pmod {9}$. There are $9$ of these, each equivalent to $11$ or $12$ integers in $[1,100]$. From the chosen $55$ numbers, one of these classes must contain at least $7$ numbers. But this implies that two of them differ by exactly $9$.

For $12$. Consider the classes $\pmod {12}$. There are $12$ of these. As before, one of these must contain $5$ numbers and we get the same implication.

For $13$. Consider the classes $\pmod {13}$. There are $13$ of these. As before, one of these must contain $5$ numbers and we get the same implication.

Answer 2

Taking lulu's method a step further, one can also show that there must be a pair in the set that differs by exactly $23$.

Consider the classes $\pmod{23}$, each containing either $4$ elements ($15$ classes) or $5$ elements ($8$ classes) of $[1,100]$. These allow $2\times 15 + 3 \times 8=54$ choices without an adjacent pair exactly $23$ apart. However we have $55$ chosen numbers so at least one of the classes has more elements than can be selected to stay non-adjacent in the class, so there must be a pair of numbers in the chosen set exactly $23$ apart.