maximum size of a subset with no two elements $x,y$ such that $x-y $ divides $x+y$ Let $A=\{1,2,3,...,2008\}$. We are going to find the maximum number of elements of $A$ such that there are no two elements $x,y$ with $x-y|x+y$. It is clear that we have to remove consecutive elements, odd consecutive,  even cosecutive numbers and numbers $pk, p(k+1)$ in general. If we start with $1$, we will find the sequence  $1,4,7,...,2008$ which is an arithmetic progression and its size is 670. But to be sure that there is no subset of $A$ with more elements, we have to show that for any subsets with 671 elements, there are such $x,y$. Could you please give me a hint how to apply pigeonhole principle to show that?
 A: Suppose there is a qualifying subset $\{a_1,...,a_{n}\}$, with $n > 670$ elements, and
$1 \le a_1 < a_2 < a_3 < ... < a_n \le 2008$.

Our goal is to derive a contradiction.

For $1\le k \le n-1$, let $g_k=a_{k+1}-a_k$.
\begin{align*}
\text{Then}\;\;&g_1 + g_2 + g_3 + \cdots + g_{n-1}\\[4pt]
=\;\;&(a_2-a_1)+(a_3-a_2)+(a_4-a_3) + \cdots + (a_n-a_{n-1})\\[4pt]
=\;\;&a_n-a_1\\[4pt]
\le\;\;&2008-1\\[4pt]
=\;\;&2007\\[4pt]
\end{align*}
Let $\bar{g}$ be the average of $g_1,g_2,g_3,...,g_{n-1}$.
\begin{align*}
\text{Then}\;\;\bar{g}\,&=\frac{g_1 + g_2 + g_3 + \cdots + g_{n-1}}{n-1}
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\;
\\[4pt]
&\le \frac{2007}{n-1}\\[4pt]
&\le \frac{2007}{670}\\[4pt]
&< 3
\end{align*}
Since $\bar{g} < 3$, we must have $g_k  = 1$ or $g_k=2$, for some $k$.

Let $x=a_{k+1}$, and let $y=a_k$.

If $g_k=1$, then $x-y=1$, so $(x-y){\,\mid\,}(x+y)$, contradiction.

If $g_k=2$, then $x-y=2$.$\;$But then $x,y$ are either both even, or both odd, and either way, $x+y$ is even, so $(x-y){\,\mid\,}(x+y)$, contradiction.

It follows that there does not exist a qualifying subset with $n > 670$.
