Let $A= {x_0, x_1, · · · , x_m}$ be a subset of ${1, 2, · · · , n}$,where $m > n/2$,show that A contains two numbers b and c such that $x_0 + b = c$.

Question

Given $A = \{a_0, a_1,...,a_m\}$ such that it's a subset of $\{1,2,...,n\}$ where $m>n/2$, and $a_0$ is the smallest number in $A$. Show that $A$ contains two numbers $b$ and $c$ such that $a_0+b=c$ with the use of the pigeonhole principle. Consider the following if stuck: $a_1-a_0, a_2-a_0,...,a_m-a_0$

Hi, I am new to this site. Please help, I have been stuck on this problem for hours now. How would you go about it?

Answer 1

Hint: Consider the set $S = \{a_1 - a_0, a_2 - a_0, \ldots, a_m - a_0\}$. If an element in $S$ is also in $A$, then this would mean that $a_p - a_0 = a_q$, for some $p, q$. Rearranging, you would get $a_0 + a_q = a_p$, so we can take $b = a_q$ and $c = a_p$.

Now the question is: Is there an element in $S$ that is also in $A$?

Answer 2

All the differences $a_1-a_0,\cdots,a_m-a_0$ are $\leq n$. These differences are all distinct, as $a_i-a_0=a_j-a_0\Rightarrow a_i=a_j$. If none of these $m$ differences belong to the set $A$, then they belong to $\{1,\cdots,n\}\setminus A$. This $1,\cdots,n$ has at least $2m$ distinct integers. Hence contradiction.