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

\[<br />
\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|.<br />
\]

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

\[<br />
\begin{split}<br />
\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\\<br />
&\leq\sum_{1\leq i<j\leq n}(|a_{j}-b_{i}|+|b_{j}-a_{i}|) \leq \\<br />
&\leq\sum_{1\leq i<j\leq n}(|a_{j}-b_{i}|+|a_{i}-b_{j}|)+\\<br />
&\qquad+\sum_{1\leq i\leq n}|a_{i}-b_{i}|=\\<br />
&=\sum_{1\leq i,j\leq n}|a_{i}-b_{j}|.<br />
\end{split}<br />
\medskip<br />
\]

Komentarze

Dodaj nową odpowiedź