Show that among the square roots of the first $ 2015 $ natural numbers, we cannot choose an arithmetic sequence composed of $ 45 $ elements.
Problem
Source: Romanian National Olympiad 2015, grade IX, p.1
Tags: arithmetic sequence, algebra, number theory
23.08.2019 15:04
CatalinBordea wrote: Show that among the square roots of the first $ 2015 $ natural numbers, we cannot choose any numbers that are in arithmetic sequence. Wrong. Choose as counter-example $\sqrt 1,\sqrt 4,\sqrt 9$
23.08.2019 15:12
Checked.
23.08.2019 15:13
CatalinBordea wrote: I think it meant 'we cannot form an arithmetic sequence of length $ (I'll figure out) $ ' I dont understand
25.08.2019 05:02
Let $\sqrt{x_o},\sqrt{x_1}, \cdots, \sqrt{x_k}$ be such a sequence, where $x_o, x_1, \cdots, x_k$ are integers in $[1,2015]$ in increasing order. Now $\sqrt{x_1}=\sqrt{x_o}+d,$ and $\sqrt{x_2}=\sqrt{x_o}+2d,$ and $\sqrt{x_k}=\sqrt{x_o}+kd,$ where $d>0,$ and $k$ a positive integer. Eliminating $d$ from the first two expressions we get $x_2=x_o+4x_1-4\sqrt{x_ox_1},\ (1)$ and $\sqrt{x_k}=k\sqrt{x_1}-(k-1)\sqrt{x_o}. \ (2)$ From $(1)$ we see that $x_ox_1$ must be a square and therefore we have two choices. First, $x_o=a^2$ and $x_1=b^2,$ where $b\ge a+1;$ therefore, from $(2),$ we get $\sqrt{x_k}\ge k(a+1)-(k-1)a=k+a\ge k+1.$ Second, $x_o=a^2b$ and $x_1=bc^2,$ where $c\ge a+1;$ therefore, from $(2),$ we get $\sqrt{x_k}\ge \sqrt{b} (kc-ka+a)\ge \sqrt{b} (k+1)\ge k+1.$ In either case, $x_k\ge (k+1)^2.$ But we want to have $x_k\le 2015$ and thus $k\le 43.$ That is, we can have at most $44$ terms in the sequence. Here is such a sequence: $\sqrt{x_o}=1,\ \sqrt{x_1}=2, \cdots,\sqrt{x_{43}}=44.$