IMO Shortlist

First, from the problem conditions we have that each $a_{n}(n>r)$ can be expressed as $a_{n}=a_{j_{1}}+a_{j_{2}}$ with $j_{1}, j_{2}<n, j_{1}+j_{2}=n$. If, say, $j_{1}>r$ then we can proceed in the same way with $a_{j_{1}}$, and so on. Finally, we represent $a_{n}$ in a form
$$\text{a n =a i 1 + +a i k 2 1 i j r, i 1 + +i k =n 3}$$
Moreover, if $a_{i_{1}}$ and $a_{i_{2}}$ are the numbers in (2) obtained on the last step, then $i_{1}+i_{2}>r$. Hence we can adjust (3) as
$$1 \leq i_{j} \leq r, \quad i_{1}+\cdots+i_{k}=n, \quad i_{1}+i_{2}>r . \tag{4}$$
On the other hand, suppose that the indices $i_{1}, \ldots, i_{k}$ satisfy the conditions (4). Then, denoting $s_{j}=i_{1}+\cdots+i_{j}$, from (1) we have
$$a_{n}=a_{s_{k}} \geq a_{s_{k-1}}+a_{i_{k}} \geq a_{s_{k-2}}+a_{i_{k-1}}+a_{i_{k}} \geq \cdots \geq a_{i_{1}}+\cdots+a_{i_{k}}$$
Summarizing these observations we get the following
Claim. For every $n>r$, we have
$$a_{n}=\max \left\{a_{i_{1}}+\cdots+a_{i_{k}}: \text{ the collection }\left(i_{1}, \ldots, i_{k}\right) \text{ satisfies }(4)\right\} .$$
Now we denote
$$s=\max _{1 \leq i \leq r} \frac{a_{i}}{i}$$
and fix some index $\ell \leq r$ such that $s=\frac{a_{\ell}}{\ell}$.
Consider some $n \geq r^{2} \ell+2 r$ and choose an expansion of $a_{n}$ in the form (2), (4). Then we have $n=i_{1}+\cdots+i_{k} \leq r k$, so $k \geq n / r \geq r \ell+2$. Suppose that none of the numbers $i_{3}, \ldots, i_{k}$ equals $\ell$. Then by the pigeonhole principle there is an index $1 \leq j \leq r$ which appears among $i_{3}, \ldots, i_{k}$ at least $\ell$ times, and surely $j \neq \ell$. Let us delete these $\ell$ occurrences of $j$ from $\left(i_{1}, \ldots, i_{k}\right)$, and add $j$ occurrences of $\ell$ instead, obtaining a sequence $\left(i_{1}, i_{2}, i_{3}', \ldots, i_{k'}'\right)$ also satisfying (4). By Claim, we have
$$a_{i_{1}}+\cdots+a_{i_{k}}=a_{n} \geq a_{i_{1}}+a_{i_{2}}+a_{i_{3}'}+\cdots+a_{i_{k'}'}$$
or, after removing the coinciding terms, $\ell a_{j} \geq j a_{\ell}$, so $\frac{a_{\ell}}{\ell} \leq \frac{a_{j}}{j}$. By the definition of $\ell$, this means that $\ell a_{j}=j a_{\ell}$, hence
$$a_{n}=a_{i_{1}}+a_{i_{2}}+a_{i_{3}'}+\cdots+a_{i_{k'}'} .$$
Thus, for every $n \geq r^{2} \ell+2 r$ we have found a representation of the form (2), (4) with $i_{j}=\ell$ for some $j \geq 3$. Rearranging the indices we may assume that $i_{k}=\ell$.
Finally, observe that in this representation, the indices $\left(i_{1}, \ldots, i_{k-1}\right)$ satisfy the conditions (4) with $n$ replaced by $n-\ell$. Thus, from the Claim we get
$$a_{n-\ell}+a_{\ell} \geq\left(a_{i_{1}}+\cdots+a_{i_{k-1}}\right)+a_{\ell}=a_{n}$$
which by (1) implies
$$a_{n}=a_{n-\ell}+a_{\ell} \quad \text{ for each } n \geq r^{2} \ell+2 r$$
as desired.

As in the previous solution, we involve the expansion (2), (3), and we fix some index $1 \leq \ell \leq r$ such that
$$\frac{a_{\ell}}{\ell}=s=\max _{1 \leq i \leq r} \frac{a_{i}}{i}$$
Now, we introduce the sequence $\left(b_{n}\right)$ as $b_{n}=a_{n}-s n$; then $b_{\ell}=0$.
We prove by induction on $n$ that $b_{n} \leq 0$, and $\left(b_{n}\right)$ satisfies the same recurrence relation as $\left(a_{n}\right)$. The base cases $n \leq r$ follow from the definition of $s$. Now, for $n>r$ from the induction hypothesis we have
$$b_{n}=\max _{1 \leq k \leq n-1}\left(a_{k}+a_{n-k}\right)-n s=\max _{1 \leq k \leq n-1}\left(b_{k}+b_{n-k}+n s\right)-n s=\max _{1 \leq k \leq n-1}\left(b_{k}+b_{n-k}\right) \leq 0,$$
as required.
Now, if $b_{k}=0$ for all $1 \leq k \leq r$, then $b_{n}=0$ for all $n$, hence $a_{n}=s n$, and the statement is trivial. Otherwise, define
$$M=\max _{1 \leq i \leq r}\left|b_{i}\right|, \quad \varepsilon=\min \left\{\left|b_{i}\right|: 1 \leq i \leq r, b_{i}<0\right\} .$$
Then for $n>r$ we obtain
$$b_{n}=\max _{1 \leq k \leq n-1}\left(b_{k}+b_{n-k}\right) \geq b_{\ell}+b_{n-\ell}=b_{n-\ell},$$
so
$$0 \geq b_{n} \geq b_{n-\ell} \geq b_{n-2 \ell} \geq \cdots \geq-M$$
Thus, in view of the expansion (2), (3) applied to the sequence $\left(b_{n}\right)$, we get that each $b_{n}$ is contained in a set
$$T=\left\{b_{i_{1}}+b_{i_{2}}+\cdots+b_{i_{k}}: i_{1}, \ldots, i_{k} \leq r\right\} \cap[-M, 0]$$
We claim that this set is finite. Actually, for any $x \in T$, let $x=b_{i_{1}}+\cdots+b_{i_{k}}\left(i_{1}, \ldots, i_{k} \leq r\right)$. Then among $b_{i_{j}}$ 's there are at most $\frac{M}{\varepsilon}$ nonzero terms (otherwise $x<\frac{M}{\varepsilon} \cdot(-\varepsilon)<-M$ ). Thus $x$ can be expressed in the same way with $k \leq \frac{M}{\varepsilon}$, and there is only a finite number of such sums.
Finally, for every $t=1,2, \ldots, \ell$ we get that the sequence
$$b_{r+t}, b_{r+t+\ell}, b_{r+t+2 \ell}, \ldots$$
is non-decreasing and attains the finite number of values; therefore it is constant from some index. Thus, the sequence $\left(b_{n}\right)$ is periodic with period $\ell$ from some index $N$, which means that
$$b_{n}=b_{n-\ell}=b_{n-\ell}+b_{\ell} \quad \text{ for all } n>N+\ell$$
and hence
$$a_{n}=b_{n}+n s=\left(b_{n-\ell}+(n-\ell) s\right)+\left(b_{\ell}+\ell s\right)=a_{n-\ell}+a_{\ell} \quad \text{ for all } n>N+\ell$$
as desired.