Probar que la estrategia greedy es la mejor.
El argumento de intercambio es una técnica de demostración súper poderosa en combinatoria y optimización, que se usa principalmente para demostrar que una estrategia "greedy" (o voraz) da una solución óptima. La idea central de un algoritmo greedy es tomar la mejor decisión local en cada paso con la esperanza de encontrar un óptimo global. El argumento de intercambio valida esto comparando la solución greedy con una solución óptima hipotética. Si la solución greedy es distinta a la óptima, el argumento demuestra que puedes intercambiar elementos dentro de la solución óptima para acercarla a la greedy sin empeorar el resultado.
Esta técnica es fundamental para resolver problemas de organización de tareas (scheduling), minimizar costos y demostrar desigualdades algebraicas como la Desigualdad de Reordenamiento. Al aplicar estos intercambios una y otra vez, puedes transformar cualquier solución óptima en la solución greedy manteniendo la optimalidad. Esto demuestra que la estructura greedy es, de hecho, el máximo o mínimo global.
La intuición se basa en identificar una "inversión" o un "cruce": un par de elementos en la solución óptima hipotética que rompe la regla de orden propuesta por el algoritmo greedy. Al mostrar que "descruzar" estos elementos (intercambiarlos para que sigan el orden greedy) mejora o mantiene el puntaje, demuestras que ningún acomodo puede ganarle al greedy. Esto transforma la búsqueda de un óptimo global en un análisis local de interacciones por pares.
Aunque el argumento de intercambio es más un método que una fórmula, su ejemplo más famoso es la Desigualdad de Reordenamiento, que sirve como el arquetipo de esta lógica.
La Desigualdad de Reordenamiento: 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, \dots, n}$, la suma de los productos cumple: $$ \sum_{i=1}^n a_i b_{n-i+1} \le \sum_{i=1}^n a_i b_{\sigma(i)} \le \sum_{i=1}^n a_i b_i $$ Esto dice que la suma es máxima cuando las sucesiones están ordenadas igual (Greedy Max) y mínima cuando están ordenadas al revés (Greedy Min).
Condición General de Intercambio: En un contexto general de optimización, si tienes una función objetivo con términos $x$ y $y$ asignados a las posiciones $A$ y $B$, el orden greedy es óptimo si el costo del acomodo "ordenado" es mejor que el del acomodo "cruzado": $$ \text{Cost}(x \to A, y \to B) \le \text{Cost}(x \to B, y \to A) $$ Esta desigualdad local suele verse así: $$ (x-y)(A-B) \ge 0 $$
Teorema: La Desigualdad de Reordenamiento (Caso de Maximización). Dados los números reales $a_1 \le a_2 \le \dots \le a_n$ y $b_1 \le b_2 \le \dots \le b_n$, la suma $S = \sum_{i=1}^n a_i b_{\sigma(i)}$ es máxima cuando $\sigma$ es la permutación identidad (es decir, cuando las $b$ están ordenadas de menor a mayor igual que las $a$).
Demostración: Toma una permutación $\sigma$ que maximice la suma $S$. Vas a usar un argumento de intercambio para mostrar que puedes transformar $\sigma$ en la permutación identidad sin que la suma disminuya.
Paso 1: Identifica una inversión Supón que $\sigma$ no es la permutación identidad. Entonces tiene que haber un par de índices $j$ y $k$ tales que $j < k$ pero $\sigma(j) > \sigma(k)$. A esto se le llama inversión. En el contexto de nuestras sucesiones, esto significa que tienes una $a$ más chica emparejada con una $b$ más grande, y una $a$ más grande con una $b$ más chica. Específicamente: $$ a_j \le a_k \quad \text{y} \quad b_{\sigma(k)} \le b_{\sigma(j)} $$
Paso 2: Haz el intercambio Considera una nueva permutación $\sigma'$ que sea idéntica a $\sigma$ excepto que intercambias las asignaciones en los índices $j$ y $k$. Es decir, $\sigma'(j) = \sigma(k)$ y $\sigma'(k) = \sigma(j)$. Sea $S$ la suma asociada con $\sigma$ y $S'$ la suma asociada con $\sigma'$.
Paso 3: Analiza el cambio en el costo Compara los términos de la suma que cambiaron. Todos los términos donde $i \neq j, k$ son iguales. $$ S' - S = (a_j b_{\sigma'(j)} + a_k b_{\sigma'(k)}) - (a_j b_{\sigma(j)} + a_k b_{\sigma(k)}) $$ Sustituyendo los valores intercambiados: $$ S' - S = (a_j b_{\sigma(k)} + a_k b_{\sigma(j)}) - (a_j b_{\sigma(j)} + a_k b_{\sigma(k)}) $$ Reacomodando los términos para factorizar: $$ S' - S = a_k(b_{\sigma(j)} - b_{\sigma(k)}) - a_j(b_{\sigma(j)} - b_{\sigma(k)}) $$ $$ S' - S = (a_k - a_j)(b_{\sigma(j)} - b_{\sigma(k)}) $$
Paso 4: Determina el signo Por el Paso 1, sabes que $j < k \implies a_j \le a_k$, así que $(a_k - a_j) \ge 0$. También identificaste que $\sigma(j) > \sigma(k)$, y como $b$ está ordenada de forma creciente, $b_{\sigma(j)} \ge b_{\sigma(k)}$. Por lo tanto, $(b_{\sigma(j)} - b_{\sigma(k)}) \ge 0$.
Como el producto de dos números no negativos es no negativo: $$ S' - S \ge 0 \implies S' \ge S $$
Conclusión El intercambio elimina la inversión $(j, k)$ y da como resultado una suma $S'$ que es al menos tan grande como $S$. Al aplicar este intercambio repetidamente a cualquier inversión, puedes transformar cualquier permutación en la identidad (la que está ordenada) sin reducir nunca la suma. Por lo tanto, el acomodo ordenado da la mayor suma posible. $\square$