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 Shortlist Problems/A1"

m (→‎Problem)
 
Line 2: Line 2:
 
(''New Zealand'')
 
(''New Zealand'')
 
You are given a sequence <math>a_1,a_2,\dots ,a_n</math> of numbers. For each <math>i</math> (<math>1\leq i\leq n</math>) define
 
You are given a sequence <math>a_1,a_2,\dots ,a_n</math> of numbers. For each <math>i</math> (<math>1\leq i\leq n</math>) define
−
 
 
<center><math>d_i=\max\{a_j:1\leq j\leq i\}-\min\{a_j:i\leq j\leq n\}</math></center>
 
<center><math>d_i=\max\{a_j:1\leq j\leq i\}-\min\{a_j:i\leq j\leq n\}</math></center>
−
 
 
and let
 
and let
−
 
 
<center><math>d=\max\{d_i:1\leq i\leq n\}</math>.</center>
 
<center><math>d=\max\{d_i:1\leq i\leq n\}</math>.</center>
−
 
 
(a) Prove that for arbitrary real numbers <math>x_1\leq x_2\leq \dots \leq x_n</math>,
 
(a) Prove that for arbitrary real numbers <math>x_1\leq x_2\leq \dots \leq x_n</math>,
−
 
 
<center><math>\max\{|x_i-a_i|:1\leq i\leq n\}\geq \frac{d}{2}</math>.</center>
 
<center><math>\max\{|x_i-a_i|:1\leq i\leq n\}\geq \frac{d}{2}</math>.</center>
−
 
 
(b) Show that there exists a sequence <math>x_1\leq x_2\leq \dots \leq x_n</math> of real numbers such that we have equality in (a).
 
(b) Show that there exists a sequence <math>x_1\leq x_2\leq \dots \leq x_n</math> of real numbers such that we have equality in (a).
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
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>, <math>1\le p\le q\le n</math>
 +
Lemma) <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.
 +
 
 +
a) Case 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 at least <math>0</math>.
 +
Case 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>.
 +
Subtracting the two inequality, we will obtain:
 +
<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>p\le q \rightarrow x_p\le x_q</math>).
 +
Thus, <math>\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}</math>
 +
 
 +
(b) A set of <math>{x_i}</math> where the equality in (*) holds is:
 +
<cmath>x_i=\max\{a_j:1\le j\le i\}-\frac{d}{2}</cmath>
 +
Since <math>\max\{a_j:1\le j\le i\}</math> is a non-decreasing function, <math>x_i</math> is non-decreasing.
 +
<math>\forall x_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>)
 +
<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>
 +
<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>
 +
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>.\\
 +
(Taken from https://artofproblemsolving.com/wiki/index.php/2007_IMO_Problems/Problem_1)
 
== Resources ==
 
== Resources ==
 
* [[2007 IMO Shortlist Problems]]
 
* [[2007 IMO Shortlist Problems]]
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]

Latest revision as of 05:11, 26 March 2024

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_IMO_Shortlist_Problems/A1&oldid=217431"