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 5 of 5: Verify equality holds for the constructed sequence

Previous step Next step

In plain words

Every term stays within $\dfrac{d}{2}$ of $a_i$ , and part (a) forces the maximum to be at least $\dfrac{d}{2}$ , so equality holds.

-\frac{d}{2} \le (M_i - a_i) - \frac{d}{2} \le \frac{d}{2} \implies \max_{1 \le i \le n} |x_i - a_i| = \frac{d}{2}

Detailed analysis

Subtracting $\dfrac{d}{2}$ from $0 \le M_i - a_i \le d$ gives $-\dfrac{d}{2} \le x_i - a_i \le \dfrac{d}{2}$ , i.e., $|x_i - a_i| \le \dfrac{d}{2}$ for all $i$ . Combined with part (a)'s lower bound $\max_i |x_i - a_i| \ge \dfrac{d}{2}$ , this gives $\max\{|x_i - a_i| : 1 \le i \le n\} = \dfrac{d}{2}$ , proving part (b).