2007 IMO Shortlist Problems/A1

Problem

(New Zealand) You are given a sequence $a_1,a_2,\dots ,a_n$ of numbers. For each $i$ ( $1\leq i\leq n$ ) define

$d_i=\max\{a_j:1\leq j\leq i\}-\min\{a_j:i\leq j\leq n\}$

and let

$d=\max\{d_i:1\leq i\leq n\}$ .

(a) Prove that for arbitrary real numbers $x_1\leq x_2\leq \dots \leq x_n$ ,

$\max\{|x_i-a_i|:1\leq i\leq n\}\geq \frac{d}{2}$ .

(b) Show that there exists a sequence $x_1\leq x_2\leq \dots \leq x_n$ of real numbers such that we have equality in (a).

Solution

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$ , $1\le p\le q\le n$ Lemma) $d\ge 0$ Assume for contradiction that $d<0$ , then for all $i$ , $a_i \le \max\{a_j:1\le j\le i\}\le \min\{a_j:i\le j\le n\}\le a_{i+1}$ $a_i\le a_{i+1}$ Then, ${a_i}$ is a non-decreasing function, which means, $\max\{a_j:1\le j\le i\}=a_i$ , and $\min\{a_j:i\le j\le n\}\le a_{i+1}=a_i$ , which means, ${d_i}={0}$ . Then, $d=0$ and contradiction.

a) Case 1) $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 2) $d>0$ (We can ignore $d<0$ because of lemma) Using the fact that $d$ can be expressed as $a_p-a_q$ for some $p$ and $q$ , $1\le p\le q\le n$ . $x_p\le x_q$ Assume for contradiction that $\max\{|x_i-a_i|:1\le i\le n\}<\dfrac{d}{2}$ . Then, $\forall x_i$ , $|x_i-a_i|<\dfrac{d}{2}$ . $|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 inequality, we will obtain: $x_p-x_q>a_p-a_q-d=a_p-a_q-a_p+a_q=0$ $x_p>x_q$ --- contradiction ( $p\le q \rightarrow x_p\le x_q$ ). Thus, $\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}$

(b) A set of ${x_i}$ where the equality in (*) holds is: $x_i=\max\{a_j:1\le j\le i\}-\frac{d}{2}$ Since $\max\{a_j:1\le j\le i\}$ is a non-decreasing function, $x_i$ is non-decreasing. $\forall x_i$ : Let $a_m=\max\{a_j:1\le j\le i\}$ , $a_m-a_i<a_m-\min\{a_j:i\le j\le n\}=d_i$ . Thus, $0\le a_m-a_i \le d$ ( $0\le a_m-a_i$ because $a_m$ is the max of a set including $a_i$ ) $|x_i-a_i|=\left|a_m-\dfrac{d}{2}-a_i\right|=\left|(a_m-a_i)\dfrac{d}{2}\right|$ $0\le a_m-a_i\le d$ $-\dfrac{d}{2} \le (a_m-a_i)\dfrac{d}{2} \le \dfrac{d}{2}$ $\left|(a_m-a_i)-\dfrac{d}{2}\right|=|x_i-a_i|\le \frac{d}{2}$ 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 x_i$ , $\max\{|x_i-a_i|:1\le i\le n\}=\dfrac{d}{2}$ .\\ (Taken from https://artofproblemsolving.com/wiki/index.php/2007_IMO_Problems/Problem_1)

Resources

2007 IMO Shortlist Problems

Page

Toolbox

Search

2007 IMO Shortlist Problems/A1

Problem

Solution

Resources