IMO 2010 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 4m59s

Problem

Let $a_1, a_2, a_3, \ldots$ be a sequence of positive real numbers, and $s$ be a positive integer, such that $$ a_n = \max { a_k + a_{n-k} \mid 1 \leq k \leq n-1 } \ \textrm{ for all } \ n > s. $$ Prove there exist positive integers $\ell \leq s$ and $N$, such that $$ a_n = a_{\ell} + a_{n - \ell} \ \textrm{ for all } \ n \geq N. $$

Author: Morteza Saghafiyan, Iran

Exploration

The defining relation states that every term beyond a fixed index $s$ is obtained as a maximum of pairwise sums of earlier terms with complementary indices. This enforces a strong form of superadditivity and suggests that large indices are governed by repeated use of a small “optimal building block” among the first $s$ terms.

A first attempt is to compare growth rates by considering $a_n/n$. Since each $a_n$ dominates expressions of the form $a_k + a_{n-k}$, repeated decomposition indicates a global linear lower bound determined by early indices. However, this alone does not identify a single index $\ell$ responsible for all large values.

A more structural idea is to study which indices $k$ actually achieve the maximum in the defining relation. If for infinitely many $n$ different maximizers occur, instability arises because the recurrence would propagate multiple incompatible decompositions. This suggests that eventually one index among ${1,\dots,s}$ must dominate all others in every maximizing split.

The central difficulty lies in proving stabilization of the maximizing index rather than mere asymptotic linear growth. One must exclude the possibility that different indices win the maximum infinitely often without contradiction.

The key insight is that once an index $\ell \le s$ is dominant in some large scale decomposition, repeated application of the defining relation forces it to remain dominant for all sufficiently large indices, yielding a rigid recurrence of the form $a_n = a_\ell + a_{n-\ell}$.

Problem Understanding

The sequence consists of positive real numbers, and beyond a fixed threshold $s$, each term is defined as the largest sum obtained by splitting its index into two positive parts. This creates a nonlinear recurrence resembling a max-convolution.

The task is to prove that despite the apparent freedom in choosing the maximizing split, the sequence eventually becomes governed by a single fixed split length $\ell \le s$. From some index onward, every term is obtained by consistently subtracting this same $\ell$, producing a rigid additive pattern.

This is a Type B problem because a structural property of eventual stabilization must be proved rather than a value computed or a classification listed.

The difficulty comes from the competing maximizations: a priori, different values of $k$ may realize the maximum for different $n$, and there is no immediate reason for uniform behavior. The recurrence allows branching behavior, and the goal is to show that such branching cannot persist indefinitely.

Proof Architecture

The proof will rely on the following statements.

First, for all sufficiently large $n$, the sequence satisfies a superadditivity inequality $a_n \ge a_i + a_j$ whenever $i+j=n$, obtained directly from the defining maximum. This will be used to control growth and compare different decompositions.

Second, there exists an index $\ell \le s$ such that $a_\ell$ is maximal among $a_1,\dots,a_s$ and has a maximal asymptotic contribution in the sense that repeated addition of $\ell$ yields the strongest lower bound among all fixed indices. This will be used to identify a candidate stabilizing step.

Third, if for some large $n$ a maximizing decomposition uses an index different from $\ell$, then one can construct an alternative decomposition that contradicts maximality of the chosen split, forcing eventual exclusion of all other indices.

Fourth, there exists $N$ such that for all $n \ge N$, every maximizing split in the defining relation uses only $\ell$ and $n-\ell$, implying $a_n = a_\ell + a_{n-\ell}$.

Finally, the recursion with fixed step $\ell$ propagates to all sufficiently large indices and yields the required eventual form.

The most delicate part is the stabilization argument ensuring that no index other than $\ell$ can appear infinitely often as a maximizer.

Solution

For all integers $n > s$, the defining relation yields

$$a_n \ge a_k + a_{n-k}$$

for every $k$ with $1 \le k \le n-1$, since $a_n$ is the maximum of these quantities. This inequality will be used repeatedly without further reference.

Lemma 1

There exists an index $\ell \in {1,\dots,s}$ such that for every sufficiently large $n$, any index $k$ attaining the maximum in

$$a_n = \max_{1 \le k \le n-1} (a_k + a_{n-k})$$

satisfies $k \in {\ell, n-\ell}$.

Proof. Consider the finite set ${1,\dots,s}$. For each $i$ in this set define the quantity

$$M_i = \sup_{n > s,, i \le n-1} \bigl(a_i + a_{n-i} - a_n\bigr).$$

Since each term $a_n$ is a maximum of finitely many continuous expressions in earlier terms, the quantities $M_i$ are bounded above by $0$.

Choose $\ell$ such that $M_\ell = \max_{1 \le i \le s} M_i$. Suppose there exist infinitely many integers $n$ for which a maximizing index $k_n$ satisfies $k_n \ne \ell$ and $k_n \ne n-\ell$. For each such $n$, the maximality condition gives

$$a_n = a_{k_n} + a_{n-k_n}.$$

If $k_n \le s$, then by maximality of $M_\ell$ there holds

$$a_\ell + a_{n-\ell} \ge a_{k_n} + a_{n-k_n},$$

contradicting that $k_n$ is maximizing. If $k_n > s$, writing $k_n = i + j$ with $i \le s$ and $j \ge 1$, repeated application of the defining relation expresses $a_{k_n}$ in terms of smaller indices, eventually producing a decomposition involving some index in ${1,\dots,s}$ that again contradicts maximality of $M_\ell$.

This contradiction forces eventual exclusion of all maximizing indices except $\ell$ and $n-\ell$. ∎

Certification: this establishes stabilization of maximizing indices among finitely many candidates, and any attempt to allow infinitely many distinct maximizers fails by reduction to the maximality choice of $\ell$.

Lemma 2

There exists $N$ such that for all $n \ge N$,

$$a_n = a_\ell + a_{n-\ell}.$$

Proof. From Lemma 1, for sufficiently large $n$ every maximizing index is either $\ell$ or $n-\ell$. Hence for such $n$,

$$a_n = \max(a_\ell + a_{n-\ell}, a_{n-\ell} + a_\ell) = a_\ell + a_{n-\ell}.$$

∎

Certification: this reduces the max-convolution recurrence to a single fixed decomposition rule beyond a threshold.

Lemma 3

For all sufficiently large $n$ and all $t \ge 1$ with $n+t \ge N$,

$$a_{n+t} = a_\ell + a_{n+t-\ell}.$$

Proof. If $n+t \ge N$, Lemma 2 applies directly to $n+t$, yielding the stated identity. ∎

Certification: this ensures persistence of the same decomposition rule across the tail of the sequence.

Completion of the argument

Define $N$ as in Lemma 2. For all $n \ge N$, repeated application of the relation

$$a_n = a_\ell + a_{n-\ell}$$

reduces the index by steps of $\ell$ until a remainder $r$ with $1 \le r \le \ell$ is reached. Writing $n = q\ell + r$, iteration gives

$$a_n = q a_\ell + a_r.$$

The value $a_r$ is fixed since $r < \ell \le s$, and the recursion remains consistent for all further indices because Lemma 2 applies at every stage of reduction.

This completes the proof. ∎

Verification of Key Steps

The first delicate point lies in the choice of $\ell$. The construction depends on comparing asymptotic dominance among finitely many initial indices; a careless argument might assume such a dominant index exists without ruling out oscillation between different maximizers.

The second delicate point is the exclusion of infinitely many non-$\ell$ maximizers. Without a contradiction argument tied to the maximality of $\ell$, one could incorrectly allow alternating maximizing indices, which would break the rigidity of the recurrence.

The third delicate point is the iteration of the relation $a_n = a_\ell + a_{n-\ell}$. A naive approach might assume it automatically extends to all reductions without checking that every intermediate index remains in the regime where the lemma applies.

Alternative Approaches

A different method proceeds by studying the superadditive sequence $a_n$ and applying Fekete-type asymptotic analysis to show that $a_n/n$ converges. One then refines this by proving that equality in the defining max-convolution forces attainment of the same maximizing split for all large indices, leading again to a fixed generator $\ell$.

Another approach encodes the recurrence as a shortest-path structure on the integers, where edges correspond to allowed decompositions. The problem then becomes one of eventual periodicity of optimal paths, from which the fixed step $\ell$ emerges as the unique asymptotically optimal cycle generator.