[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 a1, a2, … be a sequence of positive real numbers. Suppose that for some positive integers s, we have

an = max{ak + an − k | 1 ≤ k ≤ n − 1} (1)

for all n > s. Prove that there exist positive integers p and N, with p ≤ s, such that an = an − p + ap for all n ≥ N.


Proof

We first show recurrence (1) is equivalent to

an = max{ak + an − k | 1 ≤ k ≤ s} (2)

, i.e. the given a1, …, as form the basic building block as we construct the unique infinite sequence an 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 am > ak + am − k for all k in [1, s]. Assume am = an + am − 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 an = ak + an − k for some k in [1, s]. Then ak + am − k < am − n + ak + an − k, i.e. am − k < am − n + an − k, contradicting (1).

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

an = ab1 + ab2 + … + abm

where

b1 + b2 + … + bm = n, and no bi exceeds s.

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

So, a1, …, as 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 {ak} in [0, s] are already fixed, is an. Intuitively, we should use as much steep slopes as possible. Let p be in [1, s] that maximizes ap ⁄ p, i.e. the steepest slope, with arbitrary tie resolution. We will show that an = an − p + ap for any sufficiently large n.

We call any above sequence {bk} a generating sequence of an, which could have multiple generating sequences. One obvious property is that ab1 + ab2 + … + abm − 1 = ab1 + 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 an with a sufficiently large n contains at least an instance of p outside [0, s]. If this holds, we can always rearrange the sequence {bk} outside [0, s] to make it ends with p, which leads to an − p + ap = an.

Consider the sequence of slope end points when building up an, i.e. 0, b1, b1 + b2, b1 + b2 + b3, …, 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 ap without loss of optimality. The new sequence is thus a valid generating sequence with the desired slope ap, so we're done.

Q.E.D.


post by Shen-Fu Tsai


References:

[1]International Mathematical Olympiad