2007 IMO Problems/Problem 1

Problem

Real numbers $a_1, a_2, \dots , 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 \dfrac{d}{2} (*)$

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

Solution 1

Since $d_i=\max\{a_j:1\le j\le i\}-\min\{a_j:i\le j\le n\}$ , all $d_i$ can be expressed as $a_p-a_q$ where $1\le p\le i\le q \le n$ . Thus $d$ can be expressed as $a_p-a_q$ for some $p$ and $q$ with $1\le p\le q\le n$

Lemma: $d\ge 0$ .

Since $a_p \geq a_i$ and $a_i \geq a_q$ for some $i$ satisfying $p \leq i \leq q$ it follows $d \geq 0$ .

(a):

Case $d=0:$

If $d=0$ , $\max\{|x_i-a_i|:1\le i\le n\}$ is the maximum of a set of non-negative number, which must be at least $0$ .

Case $d>0:$

Assume for the sake of contradiction that $\max\{|x_i-a_i|:1\le i\le n\}<\dfrac{d}{2}$ .

Then $\forall i$ , $|x_i-a_i|<\dfrac{d}{2}$ . So $|x_p-a_p|<\dfrac{d}{2}$ and $|x_q-a_q|<\dfrac{d}{2}$ .

Thus $x_p>a_p-\dfrac{d}{2}$ and $x_q<a_q+\dfrac{d}{2}$ . Subtracting the two inequalities we obtain $x_p-x_q>a_p-a_q-d=a_p-a_q-a_p+a_q=0.$ i.e. $x_p>x_q$ which contradicts $x_p\le x_q$ (since $p \leq q$ ).

Thus $\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}$ .

(b):

A set of $x_i$ where equality holds in (*) is:

$x_i=\max\{a_j:1\le j\le i\}-\frac{d}{2}$ for all $i$ . Since $\max\{a_j:1\le j\le i\}$ is a non-decreasing function, $x_i$ is non-decreasing.

$\forall i$ let $a_{m_i}=\max\{a_j:1\le j\le i\}$ . Then $a_{m_i}-a_i<a_{m_i}-\min\{a_j:i\le j\le n\}=d_i$ .

Thus $0\le a_{m_i}-a_i \le d$ . $(0\le a_{m_i}-a_i$ because $a_m$ is the max of a set including $a_i$ ).

Therefore one has $-\dfrac{d}{2} \le a_{m_i}-a_i - \dfrac{d}{2} \le \dfrac{d}{2}$ hence $|x_i-a_i| = \left|a_{m_i}- \frac{d}{2} -a_i \right| \le \frac{d}{2}$ . Lastly since $\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}$ and $|x_i-a_i|\le \frac{d}{2} \ \forall i$ , it follows $\max\{|x_i-a_i|:1\le i\le n\}=\dfrac{d}{2}$ .

This is written by Mo Lam--- who is a horrible proof writer, so please fix the proof for me. Thank you. O, also the formatting.

(edited by not_detriti)

Solution 2

(a): Let $d_j$ satisfy $d_j = d$ . Then $\exists p,q$ with $p \leq j \leq q$ such that $d_j = a_p - a_q$ (note $a_p \geq a_j \geq a_q$ . Note this reasoning also implies $d_i \geq 0$ for all $i$ ). And for any $x_p \leq x_q$ if $x_p > a_p - d/2 = a_q + d/2$ then $|x_q-a_q| > d/2$ in which case we're done. So we may assume $x_p \leq a_p-d/2$ . But then $|x_p-a_p| \geq d/2$ and we're done.

(b): Let $f(k) = \max\{a_i : 1 \leq i \leq k\} - \max\{a_i: 1 \leq i \leq k-1\}$ for $k=2,...,n$ . Then let $\{a_{i_1},...,a_{i_m}\} = f^{-1}(0,\infty)$ such that $i_1 < \cdots < i_m$ . Let $i_0 = 1$ . Then let $j_l$ be such that $i_l \leq j_l$ and $d_{i_l} = a_{i_l} - a_{j_l}$ for $l=0,...,m$ . Note that $a_{i_0} < a_{i_1} < \cdots < a_{i_m}$ and $a_{j_0} \leq a_{j_1} \leq \cdots \leq a_{j_m}$ since $a_{j_l} = \min\{a_i: i_l \leq i \leq n\}$ .

Therefore if we set $x_i = \frac{1}{2}\big(a_{i_l}+a_{j_l} \big)\ \text{if } i_l \leq i < i_{l+1}$ and $x_i = \frac{1}{2}\big(a_{i_m} + a_{j_m}\big)\ \text{if } i_m \leq i$ one will have $x_1 \leq x_2 \leq \cdots \leq x_n$ . Furthermore if $i_l \leq i < i_{l+1}$ then $a_{i_l} \geq a_i \geq a_{j_l}$ so that $a_{i_l}-x_i = \frac{1}{2}\big(a_{i_l}-a_{j_l}\big) \geq a_i - x_i \geq a_{j_l}-x_i = \frac{1}{2}\big(-a_{i_l}+a_{j_l} \big)$ hence $|a_i-x_i| \leq \frac{1}{2}\Big(a_{i_l}-a_{j_l}\Big) = \frac{d_{i_l}}{2} \leq \frac{d}{2}.$ by definition of $d$ . A similar argument shows the above equation also holds if $i \geq i_l$ . Since $i$ was arbitrary, combined with (a) it follows equality holds in (*) for this choice of $x_1 \leq \cdots \leq x_n$ .

~not_detriti

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

2007 IMO (Problems) • Resources
Preceded by First question	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

<url>viewtopic.php?p=894656#p894656 Discussion on AoPS/MathLinks</url>

Page

Toolbox

Search

2007 IMO Problems/Problem 1

Contents

Problem

Solution 1

Solution 2

Resources