Desigualdade do Rearranjo

Essa desigualdade é bastante interessante pelo modo em que ela consegue ser extremamente simples e útil ao mesmo tempo.

A Desigualdade

Teorema (Desigualdade do Rearranjo): Sejam $a_1 \le a_2 \le ... \le a_n$ e $b_1 \le b_2 \le ... \le b_n$ sequências de reais positivos e $\sigma$ uma permutação de $(1,2,...,n)$. Então

$a_1 b_1 + a_2 b_2 +...+ a_n b_n \ge a_1 b_{ \sigma (1) } +...+ a_n b_{ \sigma (n) } \ge a_1 b_n + a_2 b_{n-1} + ...+ a_n b_1$

Prova: Vamos provar a desigualdade do lado esquerdo, sendo a outra completamente análoga.

Primeiro note que como há $n!$ permutações $\sigma$ possíveis, há uma que maximiza a expressão $a_1 b_{ \sigma (1) } +...+ a_n b_{ \sigma (n) }$. Vamos chamar essa permutação de $\pi$. Além disso, dentre todas as permutações possíveis $\pi$ que atinjam esse máximo, suponha que $\pi$ é a que minimiza a quantidade de inversões.

Se, por ventura, houver um par de inteiros $i<j$ com $\pi (i) > \pi (j)$  (ou seja, uma inversão), então note que a permutação $\pi '$ dada por $\pi$ com a troca $\pi (i) \leftrightarrow \pi (j)$, satisfaz

$a_i b_{\pi (i)} +a_j b_{\pi (j)} \le a_i b_{\pi ' (i)} + a_j b_{\pi ' (j)}$

$\Leftrightarrow 0 \le (a_j - a_i )(b_{\pi (i)} - b_{\pi (j)} )$

E essa última desigualdade é verdadeira pelo fato dos dois fatores serem não negativos.

Ou seja, $\pi '$ também atinge o valor máximo com uma quantidade menor de inversões, o que é uma contradição. Portanto a desigualdade está provada.

Para ver que a outra é análoga, basta considerar o mesmo procedimento trocando maximiza por minimiza.