Difference between revisions of "2007 IMO Problems/Problem 1"

Latest revision as of 00:12, 27 July 2025

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>

@@ Line 19: / Line 19: @@
 <hr>
-==Solution==
+==Solution 1==
-Since <math>d_i=\max\{a_j:1\le j\le i\}-\min\{a_j:i\le j\le n\}</math>, all <math>d_i</math> can be expressed as <math>a_p-a_q</math>, where <math>1\le p\le i\le q \le n</math>.
+Since <math>d_i=\max\{a_j:1\le j\le i\}-\min\{a_j:i\le j\le n\}</math>, all <math>d_i</math> can be expressed as <math>a_p-a_q</math> where <math>1\le p\le i\le q \le n</math>. Thus <math>d</math> can be expressed as <math>a_p-a_q</math> for some <math>p</math> and <math>q</math> with <math>1\le p\le q\le n</math>
-<br/>
+<b>Lemma: </b> <math>d\ge 0</math>.
-Thus, <math>d</math> can be expressed as <math>a_p-a_q</math> for some <math>p</math> and <math>q</math>, <math>1\le p\le q\le n</math>
-<br/><br/>
-<b>Lemma) </b> <math>d\ge 0</math>
-Assume for contradiction that <math>d<0</math>, then for all <math>i</math>, <math>a_i \le \max\{a_j:1\le j\le i\}\le \min\{a_j:i\le j\le n\}\le a_{i+1}</math>
-<math>a_i\le a_{i+1}</math>
-Then, <math>{a_i}</math> is a non-decreasing function, which means, <math>\max\{a_j:1\le j\le i\}=a_i</math>, and <math>\min\{a_j:i\le j\le n\}\le a_{i+1}=a_i</math>, which means, <math>{d_i}={0}</math>.
-Then, <math>d=0</math> and contradiction.
-<br/><br/>
+Since <math>a_p \geq a_i</math> and <math>a_i \geq a_q</math> for some <math>i</math> satisfying <math>p \leq i \leq q</math> it follows <math>d \geq 0</math>.
-<b>a) </b>
+<b>(a): </b>
-<b>Case </b>1) <math>d=0</math>
+<b>Case </b> <math>d=0:</math>
 If <math>d=0</math>, <math>\max\{|x_i-a_i|:1\le i\le n\}</math> is the maximum of a set of non-negative number, which must be at least <math>0</math>.
-<br/>
+<b>Case </b> <math>d>0:</math>
-<b>Case </b>2) <math>d>0</math> (We can ignore <math>d<0</math> because of lemma)
-Using the fact that <math>d</math> can be expressed as <math>a_p-a_q</math> for some <math>p</math> and <math>q</math>, <math>1\le p\le q\le n</math>. <math>x_p\le x_q</math>
-Assume for contradiction that <math>\max\{|x_i-a_i|:1\le i\le n\}<\dfrac{d}{2}</math>.
-Then, <math>\forall x_i</math>, <math>|x_i-a_i|<\dfrac{d}{2}</math>.
-<math>|x_p-a_p|<\dfrac{d}{2}</math>, and <math>|x_q-a_q|<\dfrac{d}{2}</math>
-Thus, <math>x_p>a_p-\dfrac{d}{2}</math> and <math>x_q<a_q+\dfrac{d}{2}</math>.
+Assume for the sake of contradiction that <math>\max\{|x_i-a_i|:1\le i\le n\}<\dfrac{d}{2}</math>.
-Subtracting the two inequality, we will obtain:
+Then <math>\forall i</math>, <math>|x_i-a_i|<\dfrac{d}{2}</math>. So <math>|x_p-a_p|<\dfrac{d}{2}</math> and <math>|x_q-a_q|<\dfrac{d}{2}</math>.
-<cmath>x_p-x_q>a_p-a_q-d=a_p-a_q-a_p+a_q=0</cmath>
+Thus <math>x_p>a_p-\dfrac{d}{2}</math> and <math>x_q<a_q+\dfrac{d}{2}</math>. Subtracting the two inequalities we obtain
+<cmath>
-<math>x_p>x_q</math> --- contradiction (<math>p\le q \rightarrow x_p\le x_q</math>).
+x_p-x_q>a_p-a_q-d=a_p-a_q-a_p+a_q=0.
+</cmath>
+i.e. <math>x_p>x_q</math> which contradicts <math>x_p\le x_q</math> (since <math>p \leq q</math>).
 <br/>
-Thus, <math>\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}</math>
+Thus <math>\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}</math>.
-<br/><br/>
-<b>(b) </b>
+<b>(b): </b>
-A set of <math>{x_i}</math> where the equality in (*) holds is:
+A set of <math>x_i</math> where equality holds in (*) is:
-<cmath>x_i=\max\{a_j:1\le j\le i\}-\frac{d}{2}</cmath>
+<cmath>
+x_i=\max\{a_j:1\le j\le i\}-\frac{d}{2}
-Since <math>\max\{a_j:1\le j\le i\}</math> is a non-decreasing function, <math>x_i</math> is non-decreasing.
+</cmath>
+for all <math>i</math>. Since <math>\max\{a_j:1\le j\le i\}</math> is a non-decreasing function, <math>x_i</math> is non-decreasing.
 <br/>
-<math>\forall x_i</math> :
+<math>\forall i</math> let <math>a_{m_i}=\max\{a_j:1\le j\le i\}</math>. Then <math>a_{m_i}-a_i<a_{m_i}-\min\{a_j:i\le j\le n\}=d_i</math>.
-Let <math>a_m=\max\{a_j:1\le j\le i\}</math>, <math>a_m-a_i<a_m-\min\{a_j:i\le j\le n\}=d_i</math>.
-Thus, <math>0\le a_m-a_i \le d</math> (<math>0\le a_m-a_i</math> because <math>a_m</math> is the max of a set including <math>a_i</math>)
+Thus <math>0\le a_{m_i}-a_i \le d</math>. <math>(0\le a_{m_i}-a_i</math> because <math>a_m</math> is the max of a set including <math>a_i</math>).
-<br/>
+Therefore one has
+<cmath>
+-\dfrac{d}{2} \le a_{m_i}-a_i - \dfrac{d}{2} \le \dfrac{d}{2}
+</cmath>
+hence
+<math>|x_i-a_i| = \left|a_{m_i}- \frac{d}{2} -a_i \right| \le \frac{d}{2}</math>. Lastly since <math>\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}</math> and <math>|x_i-a_i|\le \frac{d}{2} \ \forall i</math>, it follows <math>\max\{|x_i-a_i|:1\le i\le n\}=\dfrac{d}{2}</math>.
-<math>|x_i-a_i|=\left|a_m-\dfrac{d}{2}-a_i\right|=\left|(a_m-a_i)\dfrac{d}{2}\right|</math>
-<math>0\le a_m-a_i\le d</math>
+<hr/>
-<math>-\dfrac{d}{2} \le (a_m-a_i)\dfrac{d}{2} \le \dfrac{d}{2}</math>
+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.
-<math>\left|(a_m-a_i)-\dfrac{d}{2}\right|=|x_i-a_i|\le \frac{d}{2}</math>
+(edited by not_detriti)
-<br/>
+<hr/>
-Since <math>\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}</math> and <math>|x_i-a_i|\le \frac{d}{2}</math> <math>\forall x_i</math>, <math>\max\{|x_i-a_i|:1\le i\le n\}=\dfrac{d}{2}</math>
+==Solution 2==
+'''(a):''' Let <math>d_j</math> satisfy <math>d_j = d</math>. Then <math>\exists p,q</math> with <math>p \leq j \leq q</math> such that <math>d_j = a_p - a_q</math> (note <math>a_p \geq a_j \geq a_q</math>. Note this reasoning also implies <math>d_i \geq 0</math> for all <math>i</math>). And for any <math>x_p \leq x_q</math> if <math>x_p > a_p - d/2 = a_q + d/2</math> then <math>|x_q-a_q| > d/2</math> in which case we're done. So we may assume <math>x_p \leq a_p-d/2</math>. But then <math>|x_p-a_p| \geq d/2</math> and we're done.
-<hr/>
+'''(b):''' Let <math>f(k) = \max\{a_i : 1 \leq i \leq k\} - \max\{a_i: 1 \leq i \leq k-1\}</math> for <math>k=2,...,n</math>. Then let <math>\{a_{i_1},...,a_{i_m}\} = f^{-1}(0,\infty)</math> such that <math>i_1 < \cdots < i_m</math>. Let <math>i_0 = 1</math>. Then let <math>j_l</math> be such that <math>i_l \leq j_l</math> and <math>d_{i_l} = a_{i_l} - a_{j_l}</math> for <math>l=0,...,m</math>. Note that <math>a_{i_0} < a_{i_1} < \cdots < a_{i_m}</math> and <math>a_{j_0} \leq a_{j_1} \leq \cdots \leq a_{j_m}</math> since <math>a_{j_l} = \min\{a_i: i_l \leq i \leq n\}</math>.
-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.
+Therefore if we set
+<cmath>
+x_i = \frac{1}{2}\big(a_{i_l}+a_{j_l} \big)\ \text{if } i_l \leq i < i_{l+1}
+</cmath>
+and
+<cmath>
+x_i = \frac{1}{2}\big(a_{i_m} + a_{j_m}\big)\ \text{if } i_m \leq i
+</cmath>
+one will have <math>x_1 \leq x_2 \leq \cdots \leq x_n</math>. Furthermore if <math>i_l \leq i < i_{l+1}</math> then
+<math>a_{i_l} \geq a_i \geq a_{j_l}</math> so that
+<cmath>
+ 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)
+</cmath>
+hence
+<cmath>
+|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}.
+</cmath>
+by definition of <math>d</math>. A similar argument shows the above equation also holds if <math>i \geq i_l</math>. Since <math>i</math> was arbitrary, combined with (a) it follows equality holds in (*) for this choice of <math>x_1 \leq \cdots \leq x_n</math>.
-<hr/>
+~not_detriti
--->
 {{alternate solutions}}

Page

Toolbox

Search