maximum size of a subset with no two elements $x,y$ such that $x-y $ divides $x+y$

Question

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?

Answer 1

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$.