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.