Problem 1

Real numbers

a_1, a_2, \ldots, 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 exist real numbers

x_1 \le x_2 \le \cdots \le x_n

such that equality holds in the inequality above.

Step 4 of 5: Construct a non-decreasing candidate sequence for part (b)

Previous step Next step

In plain words

Tracking the running maximum and shifting it down by $\dfrac{d}{2}$ gives a non-decreasing sequence whose distance to $a_i$ is controlled by $d_i \le d$ .

M_i = \max\{a_j : 1 \le j \le i\}, \qquad x_i = M_i - \frac{d}{2}

Detailed analysis

Define $M_i = \max\{a_j : 1 \le j \le i\}$ and $x_i = M_i - \dfrac{d}{2}$ . Since $M_i \le M_{i+1}$ , the sequence $x_1 \le x_2 \le \cdots \le x_n$ is non-decreasing. Moreover $M_i \ge a_i$ (as $a_i$ is one of the terms in the maximum) and $M_i - a_i \le M_i - \min\{a_j : i \le j \le n\} = d_i \le d$ , so $0 \le M_i - a_i \le d$ for every $i$ .