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?


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

  • $\begingroup$ So nice! Thank you very much! $\endgroup$ – Fermat May 15 '18 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.