Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Resources)
m (→‎Solution)
 
(One intermediate revision by the same user not shown)
Line 44: Line 44:
 
<b>Case </b>1) <math>d=0</math>
 
<b>Case </b>1) <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 a least <math>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/>
 
<br/>
Line 64: Line 64:
 
<cmath>x_p-x_q>a_p-a_q-d=a_p-a_q-a_p+a_q=0</cmath>
 
<cmath>x_p-x_q>a_p-a_q-d=a_p-a_q-a_p+a_q=0</cmath>
  
−
<math>x_p>x_q</math> --- contradiction.
+
<math>x_p>x_q</math> --- contradiction (<math>p\le q \rightarrow x_p\le x_q</math>).
  
 
<br/>
 
<br/>
Line 96: Line 96:
 
<math>-\dfrac{d}{2} \le (a_m-a_i)\dfrac{d}{2} \le \dfrac{d}{2}</math>
 
<math>-\dfrac{d}{2} \le (a_m-a_i)\dfrac{d}{2} \le \dfrac{d}{2}</math>
  
−
<math>\left|(a_m-a_i)\dfrac{d}{2}\right|=|x_i-a_i|\le \frac{d}{2}</math>
+
<math>\left|(a_m-a_i)-\dfrac{d}{2}\right|=|x_i-a_i|\le \frac{d}{2}</math>
  
 
<br/>
 
<br/>

Latest revision as of 22:15, 31 March 2010

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

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}$


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.

--> 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>
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_IMO_Problems/Problem_1&oldid=34081"