Desigualdad del Rearreglo

Esta es una de las herramientas más intuitivas y poderosas que vas a encontrar en las matemáticas de competencia. Básicamente, nos dice que si quieres maximizar una suma de productos, debes emparejar los números más grandes con los más grandes.

Teoría

Sean $a_1 \le a_2 \le \dots \le a_n$ y $b_1 \le b_2 \le \dots \le b_n$ dos sucesiones de números reales. Para cualquier permutación $\sigma$ de ${1, 2, \dots, n}$, se cumple lo siguiente:

$$a_1 b_n + a_2 b_{n-1} + \dots + a_n b_1 \le a_1 b_{\sigma(1)} + a_2 b_{\sigma(2)} + \dots + a_n b_{\sigma(n)} \le a_1 b_1 + a_2 b_2 + \dots + a_n b_n$$

En palabras simples:

• La suma se maximiza cuando las sucesiones están ordenadas de la misma forma. A esto lo llamamos la permutación identidad.
• La suma se minimiza cuando las sucesiones están ordenadas de forma opuesta.

Intuición

Piensa en dinero. Si tienes un billete de $$10$ y uno de $$100$, y puedes multiplicarlos por $2$ o por $5$, ¿qué te daría más dinero?

• $10 \cdot 2 + 100 \cdot 5 = 20 + 500 = 520$
• $10 \cdot 5 + 100 \cdot 2 = 50 + 200 = 250$

Claramente, emparejar el multiplicador más grande con el billete más grande es la mejor opción. Este es un enfoque "voraz" (o greedy).

Demostración

La demostración estándar usa un argumento de intercambio. La idea es que si tienes una suma donde los elementos no están perfectamente ordenados, puedes encontrar una inversión y "corregirla" para aumentar el valor total.

Sea $S = a_1 b_{\sigma(1)} + \dots + a_i b_{\sigma(i)} + \dots + a_j b_{\sigma(j)} + \dots + a_n b_{\sigma(n)}$. Supón que $i < j$ pero $\sigma(i) > \sigma(j)$. Esto significa que $a_i \le a_j$ pero $b_{\sigma(j)} \le b_{\sigma(i)}$. Si intercambiamos $b_{\sigma(i)}$ y $b_{\sigma(j)}$, el cambio en la suma es:

$$(a_i b_{\sigma(j)} + a_j b_{\sigma(i)}) - (a_i b_{\sigma(i)} + a_j b_{\sigma(j)}) = (a_j - a_i)(b_{\sigma(i)} - b_{\sigma(j)})$$

Como $a_j \ge a_i$ y $b_{\sigma(i)} \ge b_{\sigma(j)}$, este producto es $\ge 0$. ¡Así que la suma se quedó igual o aumentó! Al seguir este proceso de deshacer las inversiones, eventualmente llegarás al valor máximo.

Aplicaciones

Muchas desigualdades famosas como MA-MG o Cauchy-Schwarz se pueden demostrar usando el Rearreglo.

Ejemplo

Demuestra que para números positivos $a, b, c$, se cumple $a^2 + b^2 + c^2 \ge ab + bc + ca$.

Solución: Sin perder generalidad, supón que $a \le b \le c$. Entonces las sucesiones $(a, b, c)$ y $(a, b, c)$ están ordenadas de la misma forma. Por la Desigualdad del Rearreglo, la suma de los productos por parejas es máxima cuando usamos la permutación identidad: $$a \cdot a + b \cdot b + c \cdot c = a^2 + b^2 + c^2$$

Cualquier otra permutación de la segunda sucesión, como $(b, c, a)$, nos dará una suma menor o igual: $$a \cdot b + b \cdot c + c \cdot a$$

Por lo tanto, $a^2 + b^2 + c^2 \ge ab + bc + ca$.