La suma total se mantiene igual.
El concepto de un Invariante de Suma pertenece a la clase más amplia de técnicas de invariantes que se usan en combinatoria y sistemas dinámicos. Un invariante es una propiedad de un sistema que se mantiene igual a lo largo de una secuencia de operaciones o transformaciones. Específicamente, un invariante de suma ocurre cuando la suma de los elementos en un conjunto (o una suma ponderada específica de variables) se mantiene constante, aunque los elementos individuales cambien. Esto es parecido a la conservación de la masa o la energía en física; mientras la configuración interna del sistema cambia, la "cantidad" total se queda fija.
Esta técnica es súper importante en las matemáticas de competencia para analizar procesos algorítmicos, juegos y estados alcanzables. Lo vas a usar muy seguido para demostrar resultados de imposibilidad. Si un problema te pregunta si puedes llegar a un estado objetivo desde un estado inicial, calcula la suma de los elementos de ambos. Si la operación mantiene la suma (el invariante), pero la suma inicial es diferente a la suma objetivo, entonces la transición es imposible. Por otro lado, puedes usar los invariantes de suma para determinar el estado final de un proceso sin tener que simular cada paso, simplemente sabiendo que la suma total tiene que conservarse.
La intuición clave para identificar un invariante de suma es fijarte en el cambio "local" que causa una sola operación. Si una operación reemplaza un subconjunto de números ${a, b}$ con un nuevo conjunto ${x, y}$, checa de inmediato si $a+b = x+y$. Si el cambio neto es cero, la suma global es un invariante. Este concepto suele servir como escalón para invariantes más complejos, como los monovariantes (donde la suma siempre aumenta o disminuye) o invariantes modulares (donde la suma se mantiene módulo $n$).
Imagina que tienes un estado $\mathcal{S}$ que consiste en un multiconjunto de números ${x_1, x_2, \dots, x_n}$. Lo escribimos como $S(\mathcal{S})$ para representar la suma de estos elementos: $$S(\mathcal{S}) = \sum_{i=1}^n x_i$$
La Condición del Invariante: Una operación $T$ que transforma el estado $\mathcal{S}$ en $\mathcal{S}'$ tiene un invariante de suma si: $$S(\mathcal{S}) = S(\mathcal{S}')$$ O, en términos del cambio local $\Delta$: $$\Delta = S(\mathcal{S}') - S(\mathcal{S}) = 0$$
El Teorema de Alcanzabilidad: Si una secuencia de operaciones $T_1, T_2, \dots, T_k$ transforma un estado inicial $\mathcal{S}{start}$ en un estado final $\mathcal{S}{end}$, y cada operación mantiene la suma, entonces: $$\sum_{x \in \mathcal{S}{start}} x = \sum{y \in \mathcal{S}_{end}} y$$
Manipulaciones Algebraicas Comunes que Mantienen la Suma:
Teorema: Toma un estado inicial $\mathcal{S}0$. Sea $T$ una operación permitida tal que para cualquier estado $\mathcal{S}$, el estado transformado $\mathcal{S}' = T(\mathcal{S})$ cumple que $\sum{x \in \mathcal{S}} x = \sum_{y \in \mathcal{S}'} y$. Si un estado $\mathcal{S}_{final}$ se puede alcanzar desde $\mathcal{S}0$ a través de una secuencia finita de operaciones, entonces la suma de los elementos en $\mathcal{S}{final}$ es igual a la suma de los elementos en $\mathcal{S}_0$.
Demostración: La idea es usar inducción matemática sobre el número de operaciones realizadas, que llamaremos $n$.
Sea $P(n)$ la proposición: "Si llegas a un estado $\mathcal{S}_n$ desde $\mathcal{S}_0$ después de $n$ operaciones, entonces $S(\mathcal{S}_n) = S(\mathcal{S}_0)$".
Paso 1: Caso Base ($n=0$) Después de 0 operaciones, el estado es simplemente $\mathcal{S}_0$. $$S(\mathcal{S}_0) = S(\mathcal{S}_0)$$ El caso base se cumple de forma trivial.
Paso 2: Hipótesis de Inducción Supón que para algún entero $k \geq 0$, $P(k)$ es verdadero. Es decir, para cualquier estado $\mathcal{S}_k$ al que llegues después de $k$ operaciones: $$S(\mathcal{S}_k) = S(\mathcal{S}_0)$$
Paso 3: Paso Inductivo Considera un estado $\mathcal{S}_{k+1}$ al que llegas después de $k+1$ operaciones. Este estado es el resultado de aplicar la operación $T$ a algún estado $\mathcal{S}k$ (al que llegaste después de $k$ operaciones). $$\mathcal{S}{k+1} = T(\mathcal{S}_k)$$
Por la definición de la operación $T$, la suma se mantiene durante la transición: $$S(\mathcal{S}_{k+1}) = S(\mathcal{S}_k)$$
Por la hipótesis de inducción, sabes que $S(\mathcal{S}_k) = S(\mathcal{S}0)$. Si sustituyes esto en la ecuación de arriba: $$S(\mathcal{S}{k+1}) = S(\mathcal{S}_0)$$
Por lo tanto, $P(k+1)$ es verdadero.
Conclusión: Por el Principio de Inducción Matemática, $S(\mathcal{S}_n) = S(\mathcal{S}_0)$ para todos los enteros $n \geq 0$. Por lo tanto, cualquier estado alcanzable tiene que tener la misma suma total que el estado inicial.
$\square$