IMO 2007 · Problem 1

Real numbers \(a_1,a_2,\ldots,a_n\) are given. For each \(i\) \((1\le i\le n)\) define \[ d_i=\max\{a_j:1\le j\le i\}-\min\{a_j:i\le j\le n\} \] and let \[ d=\max\{d_i:1\le i\le n\}. \]

(a) Prove that, for any real numbers \(x_1\le x_2\le\cdots\le x_n\), \[ \max\{|x_i-a_i|:1\le i\le n\}\ge \frac d2. \tag{*} \]

(b) Show that there are real numbers \(x_1\le x_2\le\cdots\le x_n\) such that equality holds in \((*)\).

Official text of the problem. Official problem paper (PDF)

Solution

Write \[ M_i=\max\{a_j:1\le j\le i\}, \qquad m_i=\min\{a_j:i\le j\le n\}. \] Thus \(d_i=M_i-m_i\). Since \(m_i\le a_i\le M_i\), we have \(d_i\ge0\).

(a) Let \(x_1\le\cdots\le x_n\) be arbitrary, and put \[ E=\max\{|x_j-a_j|:1\le j\le n\}. \] For each \(i\), choose indices \(p\le i\) and \(q\ge i\) such that \(a_p=M_i\) and \(a_q=m_i\). These indices exist because the defining sets are finite and nonempty. As \(p\le q\), we have \(x_p\le x_q\), so \[ \begin{aligned} d_i &=a_p-a_q\\ &=(a_p-x_p)+(x_p-x_q)+(x_q-a_q)\\ &\le |a_p-x_p|+|x_q-a_q|\\ &\le 2E. \end{aligned} \] Taking the maximum over \(i\) gives \(d\le2E\), proving \((*)\).

(b) Define \[ x_i=\frac{M_i+m_i}{2}\qquad(1\le i\le n). \] Both sequences \((M_i)\) and \((m_i)\) are nondecreasing: enlarging a prefix cannot decrease its maximum, and removing an element from a suffix cannot decrease its minimum. Consequently, \[ x_1\le x_2\le\cdots\le x_n. \]

Moreover, \(m_i\le a_i\le M_i\) implies \[ -\frac{M_i-m_i}{2} \le x_i-a_i \le \frac{M_i-m_i}{2}. \] Hence \[ |x_i-a_i|\le \frac{d_i}{2}\le\frac d2 \] for every \(i\). Together with part (a), this yields \[ \max\{|x_i-a_i|:1\le i\le n\}=\frac d2. \] The argument also applies when \(d=0\), including \(n=1\).

The solution was checked against the official IMO shortlist solutions.