International Mathematical Olympiad 2007 Problem 1

AlgebraInequalitiesOptimizationSeq

Real numbers a1,a2,…,ana_1, a_2, \ldots, a_n are given. For each ii (1≤i≤n1 \leq i \leq n) define

di=max⁡{aj:1≤j≤i}−min⁡{aj:i≤j≤n}d_i = \max\{a_j : 1 \leq j \leq i\} - \min\{a_j : i \leq j \leq n\}

and let

d=max⁡{di:1≤i≤n}.d = \max\{d_i : 1 \leq i \leq n\}.

(a) Prove that, for any real numbers x1≤x2≤⋯≤xnx_1 \leq x_2 \leq \cdots \leq x_n,

max⁡{∣xi−ai∣:1≤i≤n}≥d2.(∗)\max\{|x_i - a_i| : 1 \leq i \leq n\} \geq \frac{d}{2}. \quad (*)

(b) Show that there are real numbers x1≤x2≤⋯≤xnx_1 \leq x_2 \leq \cdots \leq x_n such that equality holds in (∗)(*).