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<=2s+1.

Suppose on the contrary, that there is a minimum m>2s+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]. a(k)+a(m-k)
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(b(1))+a(b(2))+...+a(b(m))

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 1 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(b(1))+a(b(2))+...+a(b(m-1))=a(b(1)+b(2)+...+b(m-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.