Track / Stage 7 / 247 of 300 #1647 of 2000

Problem 1647

National olympiad second round; IMO P1/P4

Algebra Difficulty 7.6 Prove it

9. 243 Prove: For any real numbers $a_{1}, a_{2}, \cdots, a_{n}$ , there exists a natural number $k, 1 \leqslant k \leqslant$ $n$ , such that for any $1 \geqslant b_{1} \geqslant b_{2} \cdots \geqslant b_{n} \geqslant 0$ , we have
$\left|\sum_{i=1}^{n} b_{i} a_{i}\right| \leqslant 1 \sum_{i=1}^{k} a_{i} \mid$

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

[Proof] Let $s_{0}=0, s_{i}=a_{1}+a_{2}+\cdots+a_{i}, i=1,2, \cdots, n$ , then $a_{i}=s_{i}-s_{i-1}, i=1,2, \cdots, n$ .
Thus, we have
$\begin{array}{l} \left|\sum_{i=1}^{n} b_{i} a_{i}\right|=\left|\sum_{i=1}^{n} b_{i}\left(s_{i}-s_{i-1}\right)\right|=\left|\sum_{i=1}^{n} b_{i} s_{i}-\sum_{i=1}^{n-1} b_{i+1} s_{i}\right| . \\ =\left|\sum_{i=1}^{n-1}\left(b_{i}-b_{i+1}\right) s_{i}+b_{n} s_{n}\right| \\ \leqslant \sum_{i=1}^{n-1}\left|b_{i}-b_{i+1}\right|\left|s_{i}\right|+\left|b_{n}\right|\left|s_{n}\right| \\ \text { Let } \quad\left|s_{k}\right|=\max \left\{\left|s_{1}\right|,\left|s_{2}\right|, \cdots,\left|s_{n}\right|\right\} \text { . } \end{array}$

Since $\left|b_{i}-b_{i+1}\right|=b_{i}-b_{i+1},\left|b_{n}\right|=b_{n}$ , we have
$\left|\sum_{i=1}^{n} b_{i} a_{i}\right| \leqslant\left(\sum_{i=1}^{n-1}\left(b_{i}-b_{i+1}\right)+b_{n}\right)\left|s_{k}\right|=b_{1}\left|s_{k}\right| \leqslant\left|s_{k}\right|$

That is, $\left|\sum_{i=1}^{n} b_{i} a_{i}\right| \leqslant 1 \sum_{i=1}^{k} a_{i} \mid$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.