let $A$ be a set of $n+1$ natural numbers between $1$ and $3n$. Show that there are $a,b \in A$ such that $n \leq a-b \leq 2n$

Question

I'm having difficulties solving this question and would appreciate a nudge in the right direction. I think this is best solved with pigeonhole, but what are the pigeons and what are the holes?

Answer 1

Consider the smallest element $a\in A$, where $1\le a \le 2n$.

Now, for the chosen $a\in A$, you cannot put all other $n$ integers $A\setminus\{a\}$ in the range $B=[a+1,a+n-1]$. At least one other element is in $[a+n,3n]$. If one element further satisfy $x\in[a+n,a+2n]$, or if $3n\le a+2n$, then problem solved, because $$\begin{array}{rcl} a+n\le& x &\le a+2n\\ n\le& x-a&\le 2n \end{array}$$

If not, at least one element of $A$ is in $C=[a+2n+1,3n]$. If $A\cap C = \emptyset$, that means there are less than $n+1$ elements in $A$, contradicting the problem. Notice $C$ cannot contain all other $n$ integers either; there is at least one element in $A\cap B$. Call the largest element of $A\cap B$ as $b$.

There can be at most $b-a+1\le n$ elements in $A$ less than or equal to $b$, and so there are at least $(n+1)-(b-a+1) = n-b+a$ elements greater than $b$, and they are all in $C$. The set $A\cap[b+1, a+2n]$ must be empty. If there are elements of $A$ in the range $[a+2n+1,b+2n]$, then again problem solved, because using $b\le a+n-1$, $$\begin{array}{rcl} a+2n+1\le& x&\le b+2n\\ a+2n+1-b \le& x-b &\le 2n\\ a+2n+1-(a+n-1) \le& x-b &\le 2n\\ n+2 \le& x-b &\le 2n\\ \end{array}$$

If not, the remaining elements are in $D=[b+2n+1, 3n]\subset C$. However, since there are at most $n-b$ integers in range $D$, it is impossible to fit all $n-b+a$ integers in that range, again contradicting the problem.