# [Math] International Mathematical Olympiad (IMO) 2010 Problem 6

This is a problem that I've made a couple of attempts to solve in the past few years. Eventually, perhaps encouraged by recent success of nailing IMO 3/6 problems, it is now solved.

Let *a*_{1}, *a*_{2}, … be a sequence of positive real numbers. Suppose that for some positive integers *s*, we have

*a*_{n} = max{*a*_{k} + *a*_{n − k} | 1 ≤ *k* ≤ *n* − 1} (1)

for all *n* > *s*. Prove that there exist positive integers *p* and *N*, with *p* ≤ *s*, such that *a*_{n} = *a*_{n − p} + *a*_{p} for all *n* ≥ *N*.

## Proof

We first show recurrence (1) is equivalent to

*a*_{n} = max{*a*_{k} + *a*_{n − k} | 1 ≤ *k* ≤ *s*} (2)

, i.e. the given *a*_{1}, …, *a*_{s} form the basic building block as we construct the unique infinite sequence *a*_{n} down the road. Note (2) clearly holds for *n* ≤ 2*s* + 1.

Suppose on the contrary, that there is a minimum *m* > 2*s* + 1 such that *a*_{m} > *a*_{k} + *a*_{m − k} for all *k* in [1, *s*]. Assume *a*_{m} = *a*_{n} + *a*_{m − n} for some *n* in [*s* + 1, *m* − *s* − 1], and because *m* is the smallest index violating (2) *n* doesn't violate it. So further assume *a*_{n} = *a*_{k} + *a*_{n − k} for some *k* in [1, *s*]. Then *a*_{k} + *a*_{m − k} < *a*_{m − n} + *a*_{k} + *a*_{n − k}, i.e. *a*_{m − k} < *a*_{m − n} + *a*_{n − k}, contradicting (1).

This is a significant step, because now that for each *n* > *s* we can express *a*_{n} as *a*_{k} + *a*_{n − k} for some *k* ≤ *s*, we can keep rewriting *a*_{n} to end up with

*a*_{n} = *a*_{b1} + *a*_{b2} + … + *a*_{bm}

where

*b*_{1} + *b*_{2} + … + *b*_{m} = *n*, and no *b*_{i} exceeds *s*.

(A more intuitive way is to write *a*_{n} = *a*_{k} + *a*_{m} with *k* + *m* = *n*, and rewrite *a*_{k} and/or *a*_{m} if *k* and/or *m* is larger than *s*, respectively. Keep doing it until all indexes are within [1, *s*])

So, *a*_{1}, …, *a*_{s} are like slopes and we are trying to achieve as high as possible within width *n*. The optimal height achieved, with the boundary constraint that only one slope is used within [0, *s*] because the values of sequence {*a*_{k}} in [0, *s*] are already fixed, is *a*_{n}. Intuitively, we should use as much steep slopes as possible. Let *p* be in [1, *s*] that maximizes *a*_{p} ⁄ *p*, i.e. the steepest slope, with arbitrary tie resolution. We will show that *a*_{n} = *a*_{n − p} + *a*_{p} for any sufficiently large *n*.

We call any above sequence {*b*_{k}} a generating sequence of *a*_{n}, which could have multiple generating sequences. One obvious property is that *a*_{b1} + *a*_{b2} + … + *a*_{bm − 1} = *a*_{b1 + b2 + … + bm − 1}, or more generally, every intermediate step has to be optimal too. The last step is to show that any generating sequence of *a*_{n} with a sufficiently large *n* contains at least an instance of *p* outside [0, *s*]. If this holds, we can always rearrange the sequence {*b*_{k}} outside [0, *s*] to make it ends with *p*, which leads to *a*_{n − p} + *a*_{p} = *a*_{n}.

Consider the sequence of slope end points when building up *a*_{n}, i.e. 0, *b*_{1}, *b*_{1} + *b*_{2}, *b*_{1} + *b*_{2} + *b*_{3}, …, *n*. Starting from the smallest end point outside [0, *s*], before hitting *n* there are always two end points with the same remainder when divided by *p*, as long as we see *p* slopes. These two end points span a horizontal distance divisible by *p*, so the slopes within them could all be replaced by possibly multiple *a*_{p} without loss of optimality. The new sequence is thus a valid generating sequence with the desired slope *a*_{p}, so we're done.

Q.E.D.

post by Shen-Fu Tsai

References:

[1] | International Mathematical Olympiad |