Rearrangement y Chebyshev

Desigualdad de reordenamiento: enunciado y motivación

Sean $a_1 \leq a_2 \leq \cdots \leq a_n$ y $b_1 \leq b_2 \leq \cdots \leq b_n$ dos sucesiones de números reales ordenadas de menor a mayor. La desigualdad de reordenamiento afirma que para cualquier permutación $\sigma$ de $\{1, 2, \ldots, n\}$:

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

En palabras: la suma de productos $\sum a_i b_{\sigma(i)}$ es máxima cuando los dos vectores están ordenados en el mismo sentido (ambos crecientes o ambos decrecientes), y mínima cuando están ordenados en sentidos opuestos (uno creciente y otro decreciente). Cualquier otro ordenamiento da un valor intermedio.

Intuición: "los grandes con los grandes y los pequeños con los pequeños" maximiza la suma. Si apareas el mayor $a_i$ con el mayor $b_j$, el producto es grande; si los cruzas, pierdes.

Demostración de la desigualdad de reordenamiento

Basta demostrar el máximo (la parte derecha); el mínimo es análogo. Supongamos que la permutación $\sigma$ no es la identidad; entonces existen índices $i < j$ con $\sigma(i) > \sigma(j)$ (una "inversión"). Demostramos que al "corregir" esta inversión (es decir, intercambiar $\sigma(i)$ y $\sigma(j)$) la suma no disminuye.

Sea $p = \sigma(i)$ y $q = \sigma(j)$ con $p > q$. La diferencia entre la suma con el intercambio y la suma sin él es $(a_i b_q + a_j b_p) - (a_i b_p + a_j b_q) = (a_j - a_i)(b_p - b_q)$. Como $i < j$ y las $a_i$ están ordenadas, $a_j \geq a_i$. Como $p > q$ y las $b_k$ están ordenadas, $b_p \geq b_q$. Luego $(a_j - a_i)(b_p - b_q) \geq 0$, es decir, el intercambio no reduce la suma.

Repitiendo este proceso (eliminando una inversión a la vez), llegamos a la permutación identidad sin haber disminuido la suma. Por lo tanto, la suma con la identidad (orden igual) es la mayor. El argumento es finito pues cada intercambio reduce el número de inversiones.

Desigualdad de Chebyshev como corolario

Si $a_1 \leq a_2 \leq \cdots \leq a_n$ y $b_1 \leq b_2 \leq \cdots \leq b_n$ son sucesiones que varían en el mismo sentido (ambas crecientes), entonces:

$\dfrac{a_1 b_1 + a_2 b_2 + \cdots + a_n b_n}{n} \geq \dfrac{a_1 + a_2 + \cdots + a_n}{n} \cdot \dfrac{b_1 + b_2 + \cdots + b_n}{n}$.

Si varían en sentidos opuestos, la desigualdad se invierte. La demostración: sumamos la desigualdad de reordenamiento sobre las $n!$ permutaciones $\sigma$. La suma del lado derecho (siempre la mayor) es $n \cdot \sum a_i b_i$; la suma de $\sum a_i b_{\sigma(i)}$ sobre todas las permutaciones es $\left(\sum a_i\right)\left(\sum b_j\right)$ (cada $a_i$ se empareja con cada $b_j$ exactamente $(n-1)!$ veces). Dividiendo por $n \cdot n!$: $\dfrac{\sum a_i b_i}{n} \geq \dfrac{\sum a_i}{n} \cdot \dfrac{\sum b_j}{n}$.

Ejemplo inmediato: $\dfrac{a^2 + b^2 + c^2}{3} \geq \dfrac{(a+b+c)^2}{9}$, es decir $a^2 + b^2 + c^2 \geq \dfrac{(a+b+c)^2}{3}$. Esto sigue de Chebyshev con $a_i = b_i$ (secuencias iguales, mismo sentido).

Aplicaciones olímpicas de rearrangement y Chebyshev

Problema 1 (ONEM tipo): Sean $a, b, c > 0$. Prueba que $\dfrac{a}{b} + \dfrac{b}{c} + \dfrac{c}{a} \geq 3$. Ordenamos las secuencias: tomamos $(a, b, c)$ en cualquier orden y la secuencia $(1/b, 1/c, 1/a)$ de sus recíprocos en el orden correspondiente. Como multiplicar por los valores propios (reordenamiento con igual permutación): $a \cdot \frac{1}{b} + b \cdot \frac{1}{c} + c \cdot \frac{1}{a} \geq \frac{1}{3}(a+b+c)\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right) \geq \frac{1}{3} \cdot 3 \cdot 3 = 3$ (usando AM-HM). Más directo: por AM-GM $\frac{a}{b}+\frac{b}{c}+\frac{c}{a} \geq 3\sqrt[3]{1} = 3$.

Problema 2 (Rearrangement puro): Si $a_1 \geq a_2 \geq \cdots \geq a_n > 0$, prueba que $\displaystyle\sum_{i=1}^n \dfrac{a_i^2}{a_{i+1}} \geq \sum_{i=1}^n a_i$ (índices módulo $n$). La secuencia $(a_1^2, a_2^2, \ldots, a_n^2)$ está ordenada de mayor a menor; la secuencia $(1/a_2, 1/a_3, \ldots, 1/a_1)$ es una permutación cíclica de $(1/a_1, \ldots, 1/a_n)$. Por reordenamiento, la suma con el mismo orden (que da $\sum a_i^2/a_i = \sum a_i$) es $\geq$ la suma con cualquier permutación; la suma con el orden opuesto es $\leq \sum a_i$. La permutación cíclica da $\sum a_i^2/a_{i+1} \geq \sum a_i$ (por reordenamiento, el emparejamiento "cruzado" da menos que el "recto").

Problema 3 (Chebyshev): Sea $a, b, c > 0$. Prueba que $(a^2+b^2+c^2)(a+b+c) \geq (a+b+c)(a^2+b^2+c^2)$ (trivialmente cierto), y más útilmente: $(a^3+b^3+c^3)(a+b+c) \geq (a^2+b^2+c^2)^2$. Aplicamos Chebyshev con $x_i = a_i^2$ y $y_i = a_i$ (mismo orden): $\dfrac{a^3+b^3+c^3}{3} \geq \dfrac{a^2+b^2+c^2}{3} \cdot \dfrac{a+b+c}{3}$. Multiplicando por $9$: $3(a^3+b^3+c^3) \geq (a^2+b^2+c^2)(a+b+c)$. Combinando con Cauchy-Schwarz (o AM-GM): $(a^2+b^2+c^2)^2 \leq (a^3+b^3+c^3)(a+b+c)$.