51st IMO Shortlisted Problems

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 a_{n}=a_{i_{1}}+\cdots+a_{i_{k}} \tag{2}\\ 1 \leq i_{j} \leq r, \quad i_{1}+\cdots+i_{k}=n \tag{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\le i_j\le r,i_1+\cdots +i_k=n,i_1+i_2>r.\text{\hspace{1em}(4)}$$ On the other hand, suppose that the indices $i_1,\dots ,i_k$ satisfy the conditions (4). Then, denoting $s_j=i_1+\cdots +i_j$, from (1) we have $$a_n=a_{s_k}\ge a_{s_{k-1}}+a_{i_k}\ge a_{s_{k-2}}+a_{i_{k-1}}+a_{i_k}\ge \cdots \ge 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,\dots ,i_k\right)\text{ satisfies }(4)\right\}.$$ Now we denote $$s=\underset{1\le i\le r}{\max }\frac{a_i}{i}$$ and fix some index $\ell \le r$ such that $s=\frac{a_{\ell }}{\ell }$. Consider some $n\ge r^2\ell +2r$ and choose an expansion of $a_n$ in the form (2), (4). Then we have $n=i_1+\cdots +i_k\le rk$, so $k\ge n/r\ge r\ell +2$. Suppose that none of the numbers $i_3,\dots ,i_k$ equals $\ell$. Then by the pigeonhole principle there is an index $1\le j\le r$ which appears among $i_3,\dots ,i_k$ at least $\ell$ times, and surely $j\ne \ell$. Let us delete these $\ell$ occurrences of $j$ from $\left(i_1,\dots ,i_k\right)$, and add $j$ occurrences of $\ell$ instead, obtaining a sequence $\left(i_1,i_2,i_3^{\prime },\dots ,i_{k^{\prime }}^{\prime }\right)$ also satisfying (4). By Claim, we have $$a_{i_1}+\cdots +a_{i_k}=a_n\ge a_{i_1}+a_{i_2}+a_{i_3^{\prime }}+\cdots +a_{i_{k^{\prime }}^{\prime }}$$ or, after removing the coinciding terms, $\ell a_j\ge j{a}_{\ell }$, so $\frac{a_{\ell }}{\ell }\le \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^{\prime }}+\cdots +a_{i_{k^{\prime }}^{\prime }}.$$ Thus, for every $n\ge r^2\ell +2r$ we have found a representation of the form (2), (4) with $i_j=\ell$ for some $j\ge 3$. Rearranging the indices we may assume that $i_k=\ell$. Finally, observe that in this representation, the indices $\left(i_1,\dots ,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 }\ge \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 }\text{ for each }n\ge r^2\ell +2r$$ as desired.

---

Alternative solution.

As in the previous solution, we involve the expansion (2), (3), and we fix some index $1\le \ell \le r$ such that $$\frac{a_{\ell }}{\ell }=s=\underset{1\le i\le r}{\max }\frac{a_i}{i}$$ Now, we introduce the sequence $\left(b_n\right)$ as $b_n=a_n-sn$; then $b_{\ell }=0$. We prove by induction on $n$ that $b_n\le 0$, and $\left(b_n\right)$ satisfies the same recurrence relation as $\left(a_n\right)$. The base cases $n\le r$ follow from the definition of $s$. Now, for $n>r$ from the induction hypothesis we have $$b_n=\underset{1\le k\le n-1}{\max }\left(a_k+a_{n-k}\right)-ns=\underset{1\le k\le n-1}{\max }\left(b_k+b_{n-k}+ns\right)-ns=\underset{1\le k\le n-1}{\max }\left(b_k+b_{n-k}\right)\le 0,$$ as required. Now, if $b_k=0$ for all $1\le k\le r$, then $b_n=0$ for all $n$, hence $a_n=sn$, and the statement is trivial. Otherwise, define $$M=\underset{1\le i\le r}{\max }\left|b_i\right|,\epsilon =\min \left\{\left|b_i\right|:1\le i\le r,b_i<0\right\}.$$ Then for $n>r$ we obtain $$b_n=\underset{1\le k\le n-1}{\max }\left(b_k+b_{n-k}\right)\ge b_{\ell }+b_{n-\ell }=b_{n-\ell },$$ so $$0\ge b_n\ge b_{n-\ell }\ge b_{n-2\ell }\ge \cdots \ge -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,\dots ,i_k\le 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,\dots ,i_k\le r\right)$. Then among $b_{i_j}$ 's there are at most $\frac{M}{\epsilon }$ nonzero terms (otherwise $x<\frac{M}{\epsilon }\cdot (-\epsilon )<-M$ ). Thus $x$ can be expressed in the same way with $k\le \frac{M}{\epsilon }$, and there is only a finite number of such sums. Finally, for every $t=1,2,\dots ,\ell$ we get that the sequence $$b_{r+t},b_{r+t+\ell },b_{r+t+2\ell },\dots$$ 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 }\text{ for all }n>N+\ell$$ and hence $$a_n=b_n+ns=\left(b_{n-\ell }+(n-\ell )s\right)+\left(b_{\ell }+\ell s\right)=a_{n-\ell }+a_{\ell }\text{ for all }n>N+\ell$$ as desired.