### 2007 IMO Sl #A1

Real numbers $a_{1}$, $a_{2}$, $\ldots$, $a_{n}$ are given. For each $i$, $(1 \leq i \leq n )$, define $d_{i} = \max \{ a_{j}\mid 1 \leq j \leq i \} - \min \{ a_{j}\mid i \leq j \leq n \}$ and let $d = \max \{d_{i}\mid 1 \leq i \leq n \}$.

(a) Prove that, for any real numbers $x_{1}\leq x_{2}\leq \cdots \leq x_{n}$, $\max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \}\geq \frac {d}{2}. \quad \quad (*)$

(b) Show that there are real numbers $x_{1}\leq x_{2}\leq \cdots \leq x_{n}$ such that the equality holds in (*).

a) Assume $d_m=m$ for some $m$, and let $k, l$ be the indices such that $k \le m \le l$ such that $d_m=a_k-a_l$. So, $d_m=a_k-a_l \le (a_k-x_k)+(x_l-a_l)$, which implies $a_k-x_k \ge \frac{d}{2}$ or $x_l-a_l \ge \frac{d}{2}$. The desired then follows. $\square$

b) Denote $M_i=\max\{a_j:1 \le j \le i\}$ and $m_i=\min\{a_j:1 \le j \le i\}$. Pick $x_i=\frac{m_i+M_i}{2}$. Note $m_i \le a_i \le M_i$ and the sequences $(M_i), (m_i)$ are both non-decreasing. Particularly, we have $$\frac{-d_i}{2}=\frac{m_i-M-i}{2}=x_i-M_i \le x_i-a_i.$$ Similarly, we have $x_i-a_i \le \frac{d_i}{2}$. Therefore, we can say that $$\max\{|x_i-a_i|\}: 1 \le i \le n\} \le \max\{\frac{d_i}{2}: 1 \le i \le n\}.$$ Thus, we have that equality holds in $(*)$ for our sequence $(x_i)$. $\square$