MathLabs

Problem 1

Real numbers a1,a2,…,ana_1, a_2, \ldots, a_n are given. For each ii (1≤i≤n1 \le i \le n) define di=max⁡{aj:1≤j≤i}−min⁡{aj:i≤j≤n}d_i = \max\{a_j : 1 \le j \le i\} - \min\{a_j : i \le j \le n\} and let d=max⁡{di:1≤i≤n}d = \max\{d_i : 1 \le i \le n\}. (a) Prove that, for any real numbers x1≤x2≤⋯≤xnx_1 \le x_2 \le \cdots \le x_n, max⁡{∣xi−ai∣:1≤i≤n}≥d2\max\{|x_i - a_i| : 1 \le i \le n\} \ge \dfrac{d}{2}. (b) Show that there exist real numbers x1≤x2≤⋯≤xnx_1 \le x_2 \le \cdots \le x_n such that equality holds in the inequality above.
Step 1 of 5: Realize the maximal spread as a single difference
Previous stepNext step
In plain words

The running maximum up to qq and the running minimum from qq onward are both actual terms of the sequence, so their difference is literally ap−ara_p - a_r.

d=dq=ap−ar,1≤p≤q≤r≤nd = d_q = a_p - a_r, \qquad 1 \le p \le q \le r \le n
Detailed analysis

Choose qq with d=dqd = d_q, and choose p≤q≤rp \le q \le r with ap=max⁡{aj:1≤j≤q}a_p = \max\{a_j : 1 \le j \le q\} and ar=min⁡{aj:q≤j≤n}a_r = \min\{a_j : q \le j \le n\}, so d=ap−ard = a_p - a_r. Since ap≥aq≥ara_p \ge a_q \ge a_r, we also have d≥0d \ge 0.