L OM - III - Zadanie 5

Niech $a_1,a_2, \ldots, a_n$ , $b_1,b_2, \ldots, b_n$ będą liczbami całkowitymi. Udowodnić, że

$ \sum_{1 \leq i < j \leq n}(|a_i-a_j|+|b_i-b_j|)\leq\sum_{1\leq i,j\leq n}|a_i-b_j|. $

Rozwiązanie

Sumy występujące po obu stronach danej w zadaniu nierówności nie zmienią się, jeśli w dowolny sposób zmienimy kolejność liczb $a_i$ oraz liczb $b_i$ . Bez szkody dla ogólności możemy więc założyć, że $a_1 \leq a_2 \leq \ldots \leq a_n$ oraz $b_1 \leq b_2 \leq \ldots \leq b_n$ . Wówczas

$ \begin{split} \sum_{1\leq i<j\leq n}(|a_{i}-a_{j}|+|b_{i}-b_{j}|)&=\sum_{1\leq i<j\leq n}(a_{j}-a_{i}+b_{j}-b_{i})\leq\\ &\leq\sum_{1\leq i<j\leq n}(|a_{j}-b_{i}|+|b_{j}-a_{i}|) \leq \\ &\leq\sum_{1\leq i<j\leq n}(|a_{j}-b_{i}|+|a_{i}-b_{j}|)+\\ &\qquad+\sum_{1\leq i\leq n}|a_{i}-b_{i}|=\\ &=\sum_{1\leq i,j\leq n}|a_{i}-b_{j}|. \end{split} \medskip $