[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₁, a₂, … 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₁, …, 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]. 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_b₁ + a_b₂ + … + a_{b_m}

where

b₁ + b₂ + … + 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₁, …, 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_b₁ + a_b₂ + … + a_{b_m − 1} = a_{b₁ + b₂ + … + 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₁, b₁ + b₂, b₁ + b₂ + b₃, …, 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