# 2010 IMO Problems/Problem 6

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

# 2010 IMO Problem 6 - Aadi

## 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.$$

## Solution

So for solving This Problem, we need to take a assumption that,

Let $w1 = \frac{a_{1}}{1}, w2 = \frac{a_{2}}{2}, ......, ws = \frac{a_{s}}{s}$ $\text{We claim the right choice of l is the one maximizing } w_{l}.$ $\text{Our plan is to view each } a_{n} \text{ as a linear combination of the weights } w_{1}\text{, ..., } w_{s} \text{ and track their coefficients}.$ $\text{To this end, let’s define an n-type to be a vector T = ⟨t1,...,ts⟩ of nonnegative integers such that}$
• $n = t_{1}+...+t_{s}$
• $t_{i} \text{is divisibe by i for every i}$ $T_{1} \text{ = ⟨1, 0, 0, . . . , 0⟩}$ $T_{2} \text{ = ⟨0, 2, 0, . . . , 0⟩}$ $T_{3} \text{ = ⟨0, 0, 3, . . . , 0⟩}$ $.$ $.$ $.$ $T_{s} \text{ = ⟨0, 0, 0, . . . , s⟩}$ $\text{for n = 1,..., s, respectively. Then for any n} \not\le \text{s}$ $\text{an n-type is valid if it can be written as the sum of a valid k-type and a valid (n-k)-type componentwise. These represent}$ $\text{the linear combinations possible in the recursion, in other words the recursion in the problem is phrased as}$ $a_{n} = max_{\text{(T is valid n-type)}} v(t)$ $\text{In fact, we have the following description of valid n-types:}$ $\text{Assume n} \not\le \text{s. Then an n-type ⟨}t_{1}\text{,..., }t_{s}\text{⟩ is valid if and only if either}$
• $\text{there exist indices i} \not\ge \text{j with i+j} \not\le \text{s,}t_{i}\not\le\text{i and }t_{j} \ge \text{j}$
• $\text{there exists an index i}\not\le\text{s/2 with} t_{i} \ge \text{2i}$ $\text{Proof. Immediate by forwards induction on n > s that all n-types have this property.The reverse direction is by downwards}$ $\text{induction on n. Indeed if} \sum i\frac{t_{i}}{i} \not\le 2 \text{then wemay subtract off on of {T1, . . . , Ts} while preserving the condition}$ $\text{and the case} \sum i\frac{t_{i}}{i} = 2$ $\text{Now, for each n} \not\le \text{s we pick a valid n-type } T_{n} \text{ with } a_{n} = v(T_{n})$ $\text{if there are ties, we pick one for which the } l^{th} \text{ entry is as large as possible}$ $\text{Verified by Evan Chen}$