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$