3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Double pigeonholes, nice. $\endgroup$ – Joffan Dec 9 '16 at 12:17
1
$\begingroup$

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.

$\endgroup$

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.