ISL 2007 A1

Given a sequence $a_{1}, a_{2}, \ldots, a_{n}$ of real numbers. For each $i(1 \leq i \leq n)$ define $$d_{i}=\max \left\{a_{j}: 1 \leq j \leq i\right\}-\min \left\{a_{j}: i \leq j \leq n\right\}$$ and let $$d=\max \left\{d_{i}: 1 \leq i \leq n\right\}$$ (a) Prove that for arbitrary real numbers $x_{1} \leq x_{2} \leq \ldots \leq x_{n}$, $$\max \left\{\left|x_{i}-a_{i}\right|: 1 \leq i \leq n\right\} \geq \frac{d}{2}$$ (b) Show that there exists a sequence $x_{1} \leq x_{2} \leq \ldots \leq x_{n}$ of real numbers such that we have equality in (1). (New Zealand)