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$ 
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!
 A: 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.
