International Mathematical Olympiad

Set $D=2017$. Denote $$M_n=\underset{k<n}{\max }{a}_k\text{ and }{m}_n=-\underset{k<n}{\min }{a}_k=\underset{k<n}{\max }(-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⩽M_n$, we have $a_n⩾-2M_n$.

ii. On the other hand, choose an index $k<n$ such that $a_k=M_n$. Then, we have $$a_n=-\underset{\ell <n}{\max }(a_{n-\ell }+a_{\ell })⩽-(a_{n-k}+a_k)=-a_{n-k}-M_n⩽m_n-M_n.$$ Summarizing (i) and (ii), we get $$-2M_n⩽a_n⩽m_n-M_n,$$ whence $$\begin{array}{c}{m}_n⩽m_{n+1}⩽\max \{m_n,2M_n\}\text{ and }{M}_n⩽M_{n+1}⩽\max \{M_n,m_n-M_n\}.\end{array}\text{\hspace{1em}(1)}$$

Now, say that an index $n>D$ is lucky if $m_n⩽2M_n$. Two cases are possible.

Case 1. Assume that there exists a lucky index $n$. In this case, (1) yields $m_{n+1}⩽2M_n$ and $M_n⩽M_{n+1}⩽M_n$. Therefore, $M_{n+1}=M_n$ and $m_{n+1}⩽2M_n=2M_{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⩽2M_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 $2M_n$.

Case 2. Assume now that there is no lucky index, i.e., $2M_n<m_n$ for all $n>D$. Then (1) shows that for all $n>D$ we have $m_n⩽m_{n+1}⩽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.

---

Alternative solution.

As in the previous solution, let $D=2017$. If the sequence is bounded above, say, by $Q$, then we have that $a_n⩾\min \{a_1,\dots ,a_D,-2Q\}$ 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,\dots ,a_D\}$, and $L=\max \{a_1,\dots ,a_D\}$. Call an index $n$ good if the following criteria hold: $$\begin{array}{c}{a}_n>a_i\text{ for each }i<n,a_n>-2\ell ,\text{ and }n>D\end{array}\text{\hspace{1em}(2)}$$ 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,\dots ,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⩾a_N>L,-2\ell$, and $L⩾a_i$ for every $i$ such that $1⩽i⩽D$.

Let $n$ be a good index. We derive a contradiction. We have that $$\begin{array}{c}{a}_n+a_u+a_v⩽0,\end{array}\text{\hspace{1em}(3)}$$ whenever $u+v=n$.

We define the index $u$ to maximize $a_u$ over $1⩽u⩽n-1$, and let $v=n-u$. Then, we note that $a_u⩾a_v$ by the maximality of $a_u$.

Assume first that $v⩽D$. Then, we have that $$a_N+2\ell ⩽0,$$ because $a_u⩾a_v⩾\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⩽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$.