IMO 2010 · Problem 6

Let \(a_1,a_2,a_3,\ldots\) be a sequence of positive real numbers. Suppose that for some positive integer \(s\), we have \[ a_n=\max\{a_k+a_{n-k}\mid 1\le k\le n-1\} \] for all \(n>s\). Prove that there exist positive integers \(\ell\) and \(N\), with \(\ell\le s\) and such that \(a_n=a_\ell+a_{n-\ell}\) for all \(n\ge N\).

Official text of the problem. Official problem paper (PDF)

Solution

Set \[ c=\max_{1\le i\le s}\frac{a_i}{i}, \] and choose \(\ell\in\{1,\ldots,s\}\) such that \(a_\ell=c\ell\). Define \[ b_n=cn-a_n\qquad(n\ge1). \] Then \(b_1,\ldots,b_s\) are nonnegative and \(b_\ell=0\). The given recurrence becomes \[ b_n=\min_{1\le k\le n-1}(b_k+b_{n-k}) \qquad(n>s). \tag{1} \]

We first show that every \(b_n\) is a nonnegative integer linear combination of \(b_1,\ldots,b_s\). This is immediate for \(n\le s\). For \(n>s\), choose an index \(k\) attaining the minimum in (1). Both \(k\) and \(n-k\) are smaller than \(n\), so the induction hypothesis expresses \(b_k\) and \(b_{n-k}\) as such combinations; adding them gives the required expression for \(b_n\). In particular, \[ b_n\ge0\qquad(n\ge1). \tag{2} \]

Let \[ M=\max_{1\le i\le s}b_i. \] For every \(n>s\), we have \(n>\ell\), so taking \(k=\ell\) in (1) gives \[ b_n\le b_\ell+b_{n-\ell}=b_{n-\ell}. \tag{3} \] Induction on \(n\), starting with \(1\le n\le s\), therefore yields \[ 0\le b_n\le M\qquad(n\ge1). \tag{4} \]

Consequently, the sequence \((b_n)\) takes only finitely many distinct values. Indeed, write any term as \[ b_n=\sum_{i=1}^{s}m_i b_i, \qquad m_i\in\mathbb Z_{\ge0}. \] For each \(i\) with \(b_i>0\), nonnegativity and (4) imply \[ m_i\le \left\lfloor\frac{M}{b_i}\right\rfloor. \] Thus there are only finitely many possibilities for the coefficients of the positive \(b_i\), while terms with \(b_i=0\) do not affect the sum. This also covers the case when all \(b_i\) are zero.

By (3), along each residue class modulo \(\ell\), the terms \(b_n\) are eventually nonincreasing. Since they belong to a finite set, each of these \(\ell\) subsequences must eventually be constant. Hence there is a positive integer \(N>s\) such that \[ b_n=b_{n-\ell}\qquad(n\ge N). \] Using \(a_\ell=c\ell\), we conclude that for every \(n\ge N\), \[ a_n=cn-b_n =c\ell+c(n-\ell)-b_{n-\ell} =a_\ell+a_{n-\ell}. \] The chosen \(\ell\) satisfies \(1\le\ell\le s\), as required. \(\square\)

The solution was checked against the official IMO shortlist solutions.