Prove that $\forall A_k\subset \{1,2,\dots,3n\}$, with $|A_k|=2n$, $\exists (a_i,a_j)\in A_k$ s.t. $a_i-a_j=n-1$

Question

Let $n\geq2$ be an integer. Prove that every subset $A_k\subset \{1,2,\dots,3n\}$, with $|A_k|=2n$, contains two elements $a_i,\ a_j\ $ s.t. $\ a_i-a_j=n-1$, and prove that $\nexists\ a_i,\ a_j \in A_k\ \forall k\ $ s.t. $\ a_i - a_j =n$.

It seems obvious that I will have to apply the Pigeonhole Principle, but I have no clear idea about how to start. Could you give me some hints? Thanks in advance!

Answer 1

Answer for the 1st part. Consider division with remainders $$a_i=(n-1)\cdot q_i + r_i$$ where $q_i\in\{0,1,2,3\}$ and $0\leq r_i < n-1$. We have $2n$ numbers $a_i$ (pigeons) with $n-1$ remainders $r_i$ (holes). By Pigeonhole Principle, there will be $3$ different numbers $a_{i_1},a_{i_2},a_{i_3}$ with the same remainder, or $$|a_{i_1}-a_{i_2}|=(n-1)|q_{i_1}-q_{i_2}|$$ $$|a_{i_2}-a_{i_3}|=(n-1)|q_{i_2}-q_{i_3}|$$ $$|a_{i_3}-a_{i_1}|=(n-1)|q_{i_3}-q_{i_1}|$$ A few observations:

• none of $|q_{i_1}-q_{i_2}|$, $|q_{i_2}-q_{i_3}|$, $|q_{i_3}-q_{i_1}|$ can be $0$, since $a_{i_1},a_{i_2},a_{i_3}$ are different.
• if $|q_{i_1}-q_{i_2}|=1$, $|q_{i_2}-q_{i_3}|=1$ or $|q_{i_3}-q_{i_1}|=1$ we are done. In case of (e.g.) $q_{i_1}-q_{i_2}=-1$ we simply reverse $$a_{i_2}-a_{i_1}=(n-1)(q_{i_2}-q_{i_1})=n-1$$

Now we show that at least one of $|q_{i_1}-q_{i_2}|,|q_{i_2}-q_{i_3}|,|q_{i_3}-q_{i_1}|$ is equal to $1$. We can see that $$0=(q_{i_1}-q_{i_2})+(q_{i_2}-q_{i_3})+(q_{i_3}-q_{i_1})$$ thus (again, zero is not allowed) $$\begin{array}{|c|c|c|} \hline \color{red}{q_{i_1}-q_{i_2}} & q_{i_2}-q_{i_3} & q_{i_3}-q_{i_1} \\ \hline 3 & -2 & -1 \\ \hline 3 & -1 & -2 \\ \hline -3 & 2 & 1 \\ \hline -3 & 1 & 2 \\ \hline 2 & -1 & -1 \\ \hline -2 & 1 & 1 \\ \hline \end{array}$$ and similar/symmetric results for $\color{red}{q_{i_2}-q_{i_3}}$ and $\color{red}{q_{i_3}-q_{i_1}}$ apply.