Let $X = {x_0, x_1, · · · , x_m}$ be a subset of ${1, 2, · · · , n}$, where $m > n/2$, and $x_0$ is the smallest number in $X$. Use the pigeonhole principle to show that $X$ contains two numbers $b$ and $c$ such that $x_0 + b = c$.

Also, the textbook gives a hint to consider $x_1 − x_0, x_2 − x_0, · · · , x_m − x_0$.

I can't seem to figure out this problem even with this hint...any suggestions would be great.


You want to show that there exist $i, j \in \{1,2,\dots,m\}$ such that $x_0 + x_i = x_j$. This is equivalent to $x_j - x_0 = x_i$.

Thus what you want to do is list all the numbers $x_1 - x_0, x_2 - x_0, \dots, x_m - x_0$ and show that that list has a number in common with the list $x_1, x_2, \dots, x_m$.

Each list has $m$ distinct numbers in it. If the two lists had no numbers in common, then there would be $2m$ different numbers in all, putting the two lists together. But $2m > n$, so you can't have $2m$ different numbers chosen from the set $\{1,2,\dots,n\}$. Thus the lists must have a common number.

Now say the number in common is $x_j - x_0$ in the first list and $x_i$ in the second list. Take $b = x_i$ and $c=x_j$ to finish the proof.

  • $\begingroup$ would Xm - X0 be the pigeon holes and the list X be the pigeons then? $\endgroup$ – holidayeveryday Sep 8 '14 at 4:42
  • $\begingroup$ No, $1, 2, \dots, n$ are the pigeonholes, and $x_1, x_2, \ldots, x_m, x_1 - x_0, x_2 - x_0, \ldots, x_m - x_0$ are the pigeons. $\endgroup$ – Dave Sep 8 '14 at 4:47

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.