IMO Shortlist, 2007

(a) Let $1 \leq p \leq q \leq r \leq n$ be indices for which
$$d=d_{q}, \quad a_{p}=\max \{a_{j}: 1 \leq j \leq q\}, \quad a_{r}=\min \{a_{j}: q \leq j \leq n\}$$
and thus $d=a_{p}-a_{r}$. (These indices are not necessarily unique.)

For arbitrary real numbers $x_{1} \leq x_{2} \leq \ldots \leq x_{n}$, consider just the two quantities $\left|x_{p}-a_{p}\right|$ and $\left|x_{r}-a_{r}\right|$. Since
$$\left(a_{p}-x_{p}\right)+\left(x_{r}-a_{r}\right)=\left(a_{p}-a_{r}\right)+\left(x_{r}-x_{p}\right) \geq a_{p}-a_{r}=d,$$
we have either $a_{p}-x_{p} \geq \frac{d}{2}$ or $x_{r}-a_{r} \geq \frac{d}{2}$. Hence,
$$\max \{\left|x_{i}-a_{i}\right|: 1 \leq i \leq n\} \geq \max \{\left|x_{p}-a_{p}\right|,\left|x_{r}-a_{r}\right|\} \geq \max \{a_{p}-x_{p}, x_{r}-a_{r}\} \geq \frac{d}{2}$$

(b) Define the sequence $\left(x_{k}\right)$ as
$$x_{1}=a_{1}-\frac{d}{2}, \quad x_{k}=\max \{x_{k-1}, a_{k}-\frac{d}{2}\} \quad \text{ for } 2 \leq k \leq n .$$
We show that we have equality in (1) for this sequence.
By the definition, sequence ( $x_{k}$ ) is non-decreasing and $x_{k}-a_{k} \geq-\frac{d}{2}$ for all $1 \leq k \leq n$. Next we prove that
$$\begin{equation*} x_{k}-a_{k} \leq \frac{d}{2} \quad \text{ for all } 1 \leq k \leq n \tag{2} \end{equation*}$$
Consider an arbitrary index $1 \leq k \leq n$. Let $\ell \leq k$ be the smallest index such that $x_{k}=x_{\ell}$. We have either $\ell=1$, or $\ell \geq 2$ and $x_{\ell}>x_{\ell-1}$. In both cases,
$$\begin{equation*} x_{k}=x_{\ell}=a_{\ell}-\frac{d}{2} \tag{3} \end{equation*}$$
Since
$$a_{\ell}-a_{k} \leq \max \{a_{j}: 1 \leq j \leq k\}-\min \{a_{j}: k \leq j \leq n\}=d_{k} \leq d$$
equality (3) implies
$$x_{k}-a_{k}=a_{\ell}-a_{k}-\frac{d}{2} \leq d-\frac{d}{2}=\frac{d}{2}$$
We obtained that $-\frac{d}{2} \leq x_{k}-a_{k} \leq \frac{d}{2}$ for all $1 \leq k \leq n$, so
$$\max \{\left|x_{i}-a_{i}\right|: 1 \leq i \leq n\} \leq \frac{d}{2}$$
We have equality because $\left|x_{1}-a_{1}\right|=\frac{d}{2}$.

We present another construction of a sequence ( $x_{i}$ ) for part (b).
For each $1 \leq i \leq n$, let
$$M_{i}=\max \{a_{j}: 1 \leq j \leq i\} \quad \text{ and } \quad m_{i}=\min \{a_{j}: i \leq j \leq n\} .$$
For all $1 \leq i<n$, we have
$$M_{i}=\max \{a_{1}, \ldots, a_{i}\} \leq \max \{a_{1}, \ldots, a_{i}, a_{i+1}\}=M_{i+1}$$
and
$$m_{i}=\min \{a_{i}, a_{i+1}, \ldots, a_{n}\} \leq \min \{a_{i+1}, \ldots, a_{n}\}=m_{i+1} .$$
Therefore sequences ( $M_{i}$ ) and ( $m_{i}$ ) are non-decreasing. Moreover, since $a_{i}$ is listed in both definitions,
$$m_{i} \leq a_{i} \leq M_{i}$$
To achieve equality in (1), set
$$x_{i}=\frac{M_{i}+m_{i}}{2}$$
Since sequences ( $M_{i}$ ) and ( $m_{i}$ ) are non-decreasing, this sequence is non-decreasing as well.
From $d_{i}=M_{i}-m_{i}$ we obtain that
$$-\frac{d_{i}}{2}=\frac{m_{i}-M_{i}}{2}=x_{i}-M_{i} \leq x_{i}-a_{i} \leq x_{i}-m_{i}=\frac{M_{i}-m_{i}}{2}=\frac{d_{i}}{2}$$
Therefore
$$\max \{\left|x_{i}-a_{i}\right|: 1 \leq i \leq n\} \leq \max \{\frac{d_{i}}{2}: 1 \leq i \leq n\}=\frac{d}{2}$$
Since the opposite inequality has been proved in part (a), we must have equality.