International Mathematical Olympiad

Set $D = 2017$. Denote
$$M_{n} = \max_{k < n} a_{k} \quad \text{ and } \quad m_{n} = -\min_{k < n} a_{k} = \max_{k < n} (-a_{k}) .$$
Clearly, the sequences $(m_{n})$ and $(M_{n})$ are nondecreasing. We need to prove that both are bounded.

Consider an arbitrary $n > D$; our first aim is to bound $a_{n}$ in terms of $m_{n}$ and $M_{n}$.

i. There exist indices $p$ and $q$ such that $a_{n} = - (a_{p} + a_{q})$ and $p + q = n$. Since $a_{p}, a_{q} \leqslant M_{n}$, we have $a_{n} \geqslant -2 M_{n}$.

ii. On the other hand, choose an index $k < n$ such that $a_{k} = M_{n}$. Then, we have
$$a_{n} = -\max_{\ell < n} (a_{n-\ell} + a_{\ell}) \leqslant - (a_{n-k} + a_{k}) = -a_{n-k} - M_{n} \leqslant m_{n} - M_{n} .$$
Summarizing (i) and (ii), we get
$$-2 M_{n} \leqslant a_{n} \leqslant m_{n} - M_{n},$$
whence
$$\begin{equation*} m_{n} \leqslant m_{n+1} \leqslant \max \{ m_{n}, 2 M_{n} \} \quad \text{ and } \quad M_{n} \leqslant M_{n+1} \leqslant \max \{ M_{n}, m_{n} - M_{n} \} . \tag{1} \end{equation*}$$

Now, say that an index $n > D$ is lucky if $m_{n} \leqslant 2 M_{n}$. Two cases are possible.

Case 1. Assume that there exists a lucky index $n$. In this case, (1) yields $m_{n+1} \leqslant 2 M_{n}$ and $M_{n} \leqslant M_{n+1} \leqslant M_{n}$. Therefore, $M_{n+1} = M_{n}$ and $m_{n+1} \leqslant 2 M_{n} = 2 M_{n+1}$. So, the index $n+1$ is also lucky, and $M_{n+1} = M_{n}$. Applying the same arguments repeatedly, we obtain that all indices $k > n$ are lucky (i.e., $m_{k} \leqslant 2 M_{k}$ for all these indices), and $M_{k} = M_{n}$ for all such indices. Thus, all of the $m_{k}$ and $M_{k}$ are bounded by $2 M_{n}$.

Case 2. Assume now that there is no lucky index, i.e., $2 M_{n} < m_{n}$ for all $n > D$. Then (1) shows that for all $n > D$ we have $m_{n} \leqslant m_{n+1} \leqslant m_{n}$, so $m_{n} = m_{D+1}$ for all $n > D$. Since $M_{n} < m_{n} / 2$ for all such indices, all of the $m_{n}$ and $M_{n}$ are bounded by $m_{D+1}$.

Thus, in both cases the sequences $(m_{n})$ and $(M_{n})$ are bounded, as desired.

As in the previous solution, let $D = 2017$. If the sequence is bounded above, say, by $Q$, then we have that $a_{n} \geqslant \min \{ a_{1}, \ldots, a_{D}, -2 Q \}$ for all $n$, so the sequence is bounded. Assume for sake of contradiction that the sequence is not bounded above. Let $\ell = \min \{ a_{1}, \ldots, a_{D} \}$, and $L = \max \{ a_{1}, \ldots, a_{D} \}$. Call an index $n$ good if the following criteria hold:
$$\begin{equation*} a_{n} > a_{i} \text{ for each } i < n, \quad a_{n} > -2 \ell, \quad \text{ and } \quad n > D \tag{2} \end{equation*}$$
We first show that there must be some good index $n$. By assumption, we may take an index $N$ such that $a_{N} > \max \{ L, -2 \ell \}$. Choose $n$ minimally such that $a_{n} = \max \{ a_{1}, a_{2}, \ldots, a_{N} \}$. Now, the first condition in (2) is satisfied because of the minimality of $n$, and the second and third conditions are satisfied because $a_{n} \geqslant a_{N} > L, -2 \ell$, and $L \geqslant a_{i}$ for every $i$ such that $1 \leqslant i \leqslant D$.

Let $n$ be a good index. We derive a contradiction. We have that
$$\begin{equation*} a_{n} + a_{u} + a_{v} \leqslant 0, \tag{3} \end{equation*}$$
whenever $u + v = n$.

We define the index $u$ to maximize $a_{u}$ over $1 \leqslant u \leqslant n-1$, and let $v = n - u$. Then, we note that $a_{u} \geqslant a_{v}$ by the maximality of $a_{u}$.

Assume first that $v \leqslant D$. Then, we have that
$$a_{N} + 2 \ell \leqslant 0,$$
because $a_{u} \geqslant a_{v} \geqslant \ell$. But this contradicts our assumption that $a_{n} > -2 \ell$ in the second criteria of (2).

Now assume that $v > D$. Then, there exist some indices $w_{1}, w_{2}$ summing up to $v$ such that
$$a_{v} + a_{w_{1}} + a_{w_{2}} = 0$$
But combining this with (3), we have
$$a_{n} + a_{u} \leqslant a_{w_{1}} + a_{w_{2}} .$$
Because $a_{n} > a_{u}$, we have that $\max \{ a_{w_{1}}, a_{w_{2}} \} > a_{u}$. But since each of the $w_{i}$ is less than $v$, this contradicts the maximality of $a_{u}$.