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 2 of 5: Bound the sum of the two errors at p and r
Previous stepNext step
In plain words

Rearranging the two signed deviations isolates ap−ar=da_p - a_r = d plus xr−xpx_r - x_p, which is non-negative because the sequence is non-decreasing and p≤rp \le r.

(ap−xp)+(xr−ar)=(ap−ar)+(xr−xp)≥d(a_p - x_p) + (x_r - a_r) = (a_p - a_r) + (x_r - x_p) \ge d
Detailed analysis

For any real numbers x1≤x2≤⋯≤xnx_1 \le x_2 \le \cdots \le x_n, since p≤rp \le r we have xr−xp≥0x_r - x_p \ge 0, hence (ap−xp)+(xr−ar)=(ap−ar)+(xr−xp)≥ap−ar=d(a_p - x_p) + (x_r - a_r) = (a_p - a_r) + (x_r - x_p) \ge a_p - a_r = d.