Maths Olympiad Prep

Library / /473 of 520

Algebra Difficulty 5.9 AIME, harder Prove it

Example 6. (Chebyshev's Inequality) Let a1a2an,b1b2bna_{1} \leqslant a_{2} \leqslant \cdots \leqslant a_{n}, b_{1} \leqslant b_{2} \leqslant \cdots \leqslant b_{n}, then
k=1nakbnk+11n(k=1nak)(k=1nbk)k=1nakbk. \begin{array}{l} \sum_{k=1}^{n} a_{k} b_{n-k+1} \leqslant \frac{1}{n}\left(\sum_{k=1}^{n} a_{k}\right) \\ \cdot\left(\sum_{k=1}^{n} b_{k}\right) \leqslant \sum_{k=1}^{n} a_{k} b_{k} . \end{array}

Solution

Proof: Let {tr}\{t_{r}\} be a periodic sequence with period nn. When 1kn1 \leqslant k \leqslant n, tk=bkt_{k}=b_{k}. Let Ak=tk+mbkA_{k}=t_{k+m}-b_{k} (1kn,m=0,1,2,,n1)(1 \leqslant k \leqslant n, m=0,1,2, \cdots, n-1). By (I), the sequence {Ak}\{A_{k}\} satisfies Sn=0,Sk0S_{n}=0, S_{k} \geqslant 0 (1kn11 \leqslant k \leqslant n-1). Therefore, by Theorem (1), we have
Tn=i=1naiAi=i=1nai(ti+mbi)0, T_{n}=\sum_{i=1}^{n} a_{i} A_{i}=\sum_{i=1}^{n} a_{i}\left(t_{i+m}-b_{i}\right) \leqslant 0,

which implies i=1naibii=1naiti+m\sum_{i=1}^{n} a_{i} b_{i} \geqslant \sum_{i=1}^{n} a_{i} t_{i+m}, for m=0,1,2,,n1m=0,1,2, \cdots, n-1. Summing both sides over m=0,1,2,,n1m=0,1,2, \cdots, n-1, we get
ni=1naibi(i=1nai)(i=1nbi). n \sum_{i=1}^{n} a_{i} b_{i} \geqslant\left(\sum_{i=1}^{n} a_{i}\right) \cdot\left(\sum_{i=1}^{n} b_{i}\right).

This proves the right-hand side of the inequality.
Now let Ai=bni+1ti+m(1in,m=0,1,2,,n1), by (II), the sequence {Ai} satisfies Sn=0,Sk0(1kn1). Therefore, by Theorem (1), we have  \text{Now let } A_{i}^{\prime}=b_{n-i+1}-t_{i+m} (1 \leqslant i \leqslant n, \\ m=0,1,2, \cdots, n-1), \text{ by (II), the sequence } \{A_{i}^{\prime}\} \text{ satisfies } S_{n}=0, S_{k} \geqslant 0 (1 \leqslant k \leqslant n-1). \text{ Therefore, by Theorem (1), we have }
Tn=i=1naiAi=i=1nai(bni+1ti+m)0, \begin{aligned} T_{n}^{\prime} & =\sum_{i=1}^{n} a_{i} A_{i}^{\prime}=\sum_{i=1}^{n} a_{i}\left(b_{n-i+1}-t_{i+m}\right) \\ & \leqslant 0, \end{aligned}
which implies i=1naibni+1i=1naiti+m,m=0,1,2,,n1. \begin{array}{l} \text{which implies } \sum_{i=1}^{n} a_{i} b_{n-i+1} \leqslant \sum_{i=1}^{n} a_{i} t_{i+m}, m=0, \\ 1,2, \cdots, n-1. \end{array}

Summing both sides over mm yields the left-hand side of the original inequality.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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