Serbian Mathematical Olympiad

Solution:

Let us consider the two smallest (distinct) terms of the sequence, $p$ and $q$. If $\min \{p, q\}= 1$, the claim trivially holds; hence from now on we assume $p, q>1$.

Lemma 1. There exist indices $k$ and $l$ such that $a_{k}=p, a_{l}=q$ and $|k-l| \leq 2$.

Proof. Let $a_{k}=p$ and $a_{l}=q$ ($k<l$). Suppose that $r=l-k>2$. We shall prove by induction on $r$ that for some $i$, $k<i<l$, we have $a_{i} \in\{p, q\}$. Since $a_{k+3} \neq\left|a_{k+2}-a_{k+1}\right|=p$, we have $a_{k+3}=a_{k+1}+a_{k+2}$; similarly $a_{l-3}=a_{l-2}+a_{l-1}$. Let $a_{m}=\max _{p<i<q} a_{i}$. It is clear that $k+2<m<l-2$ (hence $l-k \geqslant 6$), and also $a_{m+2}=a_{m}-a_{m+1}=a_{m-1}$ and $a_{m+1}=a_{m}-a_{m-1}=a_{m-2}$. This means that the sequence $\left(a_{i}^{\prime}\right)$, defined by $a_{i}^{\prime}=a_{i}$ for $i<m$ and $a_{i}^{\prime}=a_{i+3}$ for $i \geqslant m$, satisfies the conditions of the problem; moreover $a_{k}^{\prime}=p$ and $a_{l-3}^{\prime}=q$, so by the inductive hypothesis (since $(l-3)-k \geqslant 3$) we have $a_{i}^{\prime} \in\{p, q\}$ for some $i$ ($k<i<l-3$). Then also $a_{i} \in\{p, q\}$ or $a_{i+3} \in\{p, q\}$, which completes the induction.

Lemma 2. For every $i$ ($0 \leqslant i \leqslant n$) there exist $x_{i}, y_{i} \in \mathbb{N}_{0}$ such that $a_{i}=x_{i} p+y_{i} q$ and $\left(x_{i}, y_{i}\right)=1$.

Proof. Let us consider the vectors $v_{k}=(1,0)$ and $v_{l}=(0,1)$ and, for every $i$, define $v_{i+2}=\varepsilon_{i} v_{i}+\varepsilon_{i}^{\prime} v_{i+1}$ if $a_{i+2}=\varepsilon_{i} a_{i}+\varepsilon_{i}^{\prime} a_{i+1}$ ($\varepsilon_{i}, \varepsilon_{i}^{\prime} \in\{-1,1\}$). By a simple induction we get that for $v_{i}=(x_{i}, y_{i})$ we have
$$a_{i}=x_{i} p+y_{i} q$$
Since $x_{i+1} y_{i+2}-x_{i+2} y_{i+1}=x_{i+1}\left(\varepsilon_{i} y_{i}+\varepsilon_{i}^{\prime} y_{i+1}\right)-\left(\varepsilon_{i} x_{i}+\varepsilon_{i}^{\prime} x_{i+1}\right) y_{i+1}=-\varepsilon_{i}\left(x_{i} y_{i+1}-x_{i+1} y_{i}\right)$ and similarly $x_{i} y_{i+2}-x_{i+2} y_{i}=\varepsilon_{i}^{\prime}\left(x_{i} y_{i+1}-x_{i+1} y_{i}\right)$, we have
$$x_{i} y_{i+1}-x_{i+1} y_{i}, x_{i} y_{i+2}-x_{i+2} y_{i} \in\{-1,1\} \text{ for } 0 \leqslant i<n$$
and from this $\left(x_{i}, y_{i}\right)=1$. It remains to show that $x_{i}, y_{i} \geqslant 0$ for all $i$.

Suppose that $x_{i}<0$ for some $i<k$ (the case $y_{i}<0$ and/or $i>l$ is analogous) and consider the largest such $i$. Since $a_{i}>0$ and (1), we have $y_{i}>0$. From (2) and $x_{i} y_{i+1}, x_{i} y_{i+2} \leqslant 0 \leqslant x_{i+1} y_{i}, x_{i+2} y_{i}$ it follows that $v_{i+1}$, $v_{i+2} \in\{(0,1),(1,0)\}$, and then it must be that $v_{i}= \pm(1,-1)$, i.e. $a_{i}=|p-q|$. However, since $p$ and $q$ are coprime and greater than 1, we have $\max \{p, q\}>|p-q| \notin\{p, q\}$, contrary to the choice of $p$ and $q$.

Let $m=d a_{0}=e a_{n}$. By Lemma 2 we have $m=d x_{0} p+d y_{0} q=e x_{n} p+e y_{n} q$, where $\left(d x_{0}, d y_{0}\right) \neq\left(e x_{n}, e y_{n}\right)$ since because of $a_{0} \neq a_{n}$ we have $\frac{x_{0}}{y_{0}} \neq \frac{x_{n}}{y_{n}}$. From this it follows that $p \mid d y_{0}-e y_{n}$, so $d y_{0}>p$ or $e y_{n}>p$; finally, $m>p q$ and therefore $\min (p, q)<\sqrt{m}$.