Maths Olympiad Prep

Track / Stage 7 / 144 of 300 #1544 of 1964

Problem 1544

National olympiad second round; IMO P1/P4
Algebra Difficulty 7.3 Prove it

13. a1,a2,⋯ ,an;b1,b2,⋯ ,bna_{1}, a_{2}, \cdots, a_{n} ; b_{1}, b_{2}, \cdots, b_{n} are two sequences of positive real numbers, prove: ∑1⩽i<j⩽n(∣ai−aj∣+\sum_{1 \leqslant i<j \leqslant n}\left(\mid a_{i}-a_{j} \mid+\right. ∣bi−bj∣)⩽∑1⩽i<j⩽n∣ai−bj∣.(1999−\left.\left|b_{i}-b_{j}\right|\right) \leqslant \sum_{1 \leqslant i<j \leqslant n}\left|a_{i}-b_{j}\right| .(1999- Poland Mathematical Olympiad problem)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

13. By symmetry, without loss of generality, assume a1⩽a2⩽⋯⩽an,b1⩽b2⩽⋯⩽bna_{1} \leqslant a_{2} \leqslant \cdots \leqslant a_{n}, b_{1} \leqslant b_{2} \leqslant \cdots \leqslant b_{n}, so
∑1⩽i<j⩽n(∣ai−aj∣+∣bi−bj∣)=∑1⩽i<j⩽i(aj−ai+bj−bi)=∑1⩽i<j⩽n[(aj−bi)+(bj−ai)]⩽∑i⩽<j⩽n∣aj−bi∣+∑1⩽i<j⩽n∣bj−ai∣⩽∑1⩽i<j⩽n∣aj−bi∣+∑1⩽i<j⩽n∣aj−bj∣+∑∣⩽i⩽n∣ai−bi∣=∑1∑i<j∣⩽n∣ai−bj∣\begin{array}{l} \sum_{1 \leqslant i<j \leqslant n}\left(\left|a_{i}-a_{j}\right|+\left|b_{i}-b_{j}\right|\right)= \\ \sum_{1 \leqslant i<j \leqslant i}\left(a_{j}-a_{i}+b_{j}-b_{i}\right)= \\ \sum_{1 \leqslant i<j \leqslant n}\left[\left(a_{j}-b_{i}\right)+\left(b_{j}-a_{i}\right)\right] \leqslant \\ \sum_{i \leqslant<j \leqslant n}\left|a_{j}-b_{i}\right|+\sum_{1 \leqslant i<j \leqslant n}\left|b_{j}-a_{i}\right| \leqslant \\ \sum_{1 \leqslant i<j \leqslant n}\left|a_{j}-b_{i}\right|+\sum_{1 \leqslant i<j \leqslant n}\left|a_{j}-b_{j}\right|+\sum_{\mid \leqslant i \leqslant n}\left|a_{i}-b_{i}\right|= \\ \sum_{1 \sum_{i<j} \mid \leqslant n}\left|a_{i}-b_{j}\right| \end{array}

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