2007 IMO Shortlist Problems/A1
Problem
(New Zealand)
You are given a sequence of numbers. For each
(
) define
![$d_i=\max\{a_j:1\leq j\leq i\}-\min\{a_j:i\leq j\leq n\}$](http://latex.artofproblemsolving.com/1/8/9/189de4c31e3bbc18f2a728546428ea8bb222bebe.png)
and let
![$d=\max\{d_i:1\leq i\leq n\}$](http://latex.artofproblemsolving.com/7/f/d/7fdc1b9fb65f8df2b3b292342c6e1b2d77c44e21.png)
(a) Prove that for arbitrary real numbers ,
![$\max\{|x_i-a_i|:1\leq i\leq n\}\geq \frac{d}{2}$](http://latex.artofproblemsolving.com/e/d/8/ed80966e31623d83b93ce2db9fdac05d04549dac.png)
(b) Show that there exists a sequence of real numbers such that we have equality in (a).
Solution
Since , all
can be expressed as
, where
.
Thus,
can be expressed as
for some
and
,
Lemma)
Assume for contradiction that
, then for all
,
Then,
is a non-decreasing function, which means,
, and
, which means,
.
Then,
and contradiction.
a) Case 1)
If
,
is the maximum of a set of non-negative number, which must be at least
.
Case 2)
(We can ignore
because of lemma)
Using the fact that
can be expressed as
for some
and
,
.
Assume for contradiction that
.
Then,
,
.
, and
Thus,
and
.
Subtracting the two inequality, we will obtain:
--- contradiction (
).
Thus,
(b) A set of where the equality in (*) holds is:
Since
is a non-decreasing function,
is non-decreasing.
:
Let
,
.
Thus,
(
because
is the max of a set including
)
Since
and
,
.\\
(Taken from https://artofproblemsolving.com/wiki/index.php/2007_IMO_Problems/Problem_1)