Sumas de Verificación de Paridad

Teoría

Las sumas de verificación de paridad (Parity Checksums) son una clase específica de invariantes que se usan en la teoría de juegos combinatorios y en procesos algorítmicos. La técnica consiste en calcular la suma de un conjunto de valores numéricos asociados al estado de un sistema y analizar esta suma módulo 2. Aunque los valores individuales del sistema cambien drásticamente mediante operaciones complejas, la paridad (si es par o impar) de su suma total a menudo se mantiene constante o alterna de manera predecible. Si una operación permitida cambia la suma total de los elementos por un número par, la paridad de la suma es un invariante.

Esta técnica es fundamental para demostrar resultados de imposibilidad. En problemas que preguntan si puedes llegar a un estado final específico desde un estado inicial dado (como en la manipulación de cuadrículas, lanzamientos de monedas o juegos de reemplazar números), la suma de verificación de paridad ofrece una condición necesaria para que sea posible llegar a ese estado. Si el estado inicial tiene una suma con paridad $P_{start}$ y el estado objetivo tiene una suma con paridad $P_{end}$, y resulta que $P_{start} \neq P_{end}$, entonces la transformación es imposible, siempre y cuando las operaciones conserven la paridad de la suma.

La intuición detrás de las sumas de verificación de paridad se basa en las propiedades de la aritmética modular. Muchas operaciones afectan a los elementos en pares o grupos, de tal forma que el cambio neto en el valor total del sistema es $0$, $\pm 2$, o algún otro múltiplo de $2$. Por ejemplo, si eliges dos números $a$ y $b$ y los reemplazas por $a-1$ y $b-1$, la suma disminuye en $2$. Aunque la suma cambie, su residuo módulo 2 no lo hace. Esto te permite ignorar la complejidad de los pasos intermedios y enfocarte únicamente en la característica binaria de la "masa" total del sistema.

Fórmulas Clave

Definición de la suma de verificación: Dado un estado definido por un conjunto de variables $X = {x_1, x_2, \dots, x_n}$, la suma de verificación de paridad $S$ la definimos como: $$S \equiv \sum_{i=1}^n x_i \pmod 2$$

La condición de invarianza: Supón que una operación transforma el conjunto $X$ en $X'$, resultando en una nueva suma $S'$. La paridad es invariante si el cambio en la suma, que escribimos como $\Delta \Sigma$, cumple que: $$\Delta \Sigma = \sum_{i=1}^n x'i - \sum{i=1}^n x_i = 2k \quad \text{para algún } k \in \mathbb{Z}$$ Esto implica que: $$S' \equiv S \pmod 2$$

Principio de imposibilidad: Si un sistema comienza en el estado $A$ y busca llegar al estado $B$, y las operaciones permitidas conservan la paridad de la suma, entonces: $$\sum_{x \in A} x \not\equiv \sum_{y \in B} y \pmod 2 \implies \text{El estado } B \text{ es inalcanzable desde } A$$

Lema del apretón de manos (Aplicación en teoría de gráficas): En una gráfica $G=(V, E)$, la suma de los grados es el doble del número de aristas. Esta es una identidad clásica de suma de verificación de paridad: $$\sum_{v \in V} \deg(v) = 2|E| \equiv 0 \pmod 2$$ Corolario: El número de vértices con grados impares tiene que ser par.

Demostración

Teorema: Sea $S_t$ la suma de los elementos de un sistema en el paso $t$. Si cada operación válida cambia la suma total por un entero par, entonces la paridad de la suma es invariante para todo $t \ge 0$. Por lo tanto, un estado objetivo con una suma de paridad diferente es inalcanzable.

Demostración:

1. Caso base: Supón que el estado inicial en $t=0$ consiste de los elementos ${x_{1}, x_{2}, \dots, x_{n}}$. La suma inicial es $S_0 = \sum_{i=1}^n x_{i}$. La paridad del sistema la determina $S_0 \pmod 2$.

2. Paso inductivo: Supón que en el paso $t$, la suma es $S_t$. Aplicas una operación válida para pasar al paso $t+1$. Deja que la operación modifique un subconjunto de elementos. Los nuevos valores los escribimos con primas ($'$). La nueva suma es $S_{t+1}$.

   El cambio en la suma está dado por $\Delta S = S_{t+1} - S_t$.

   Por la hipótesis del teorema, cualquier operación válida cambia la suma total por un entero par. Por lo tanto, existe un entero $k$ tal que: $$\Delta S = 2k$$

3. Aritmética modular: Analiza la relación entre $S_{t+1}$ y $S_t$ módulo 2: $$S_{t+1} = S_t + 2k$$ Al tomar ambos lados módulo 2: $$S_{t+1} \equiv S_t + 2k \pmod 2$$ Como $2k \equiv 0 \pmod 2$ para cualquier entero $k$: $$S_{t+1} \equiv S_t \pmod 2$$

4. Conclusión de la invarianza: Por inducción, para cualquier número de pasos $N$, se cumple que $S_N \equiv S_0 \pmod 2$. La paridad de la suma se mantiene constante durante todo el proceso.

5. Demostración de imposibilidad (Contradicción): Supón que quieres llegar a un estado objetivo con una suma $S_{target}$ tal que $S_{target} \not\equiv S_0 \pmod 2$. Imagina que este estado es alcanzable después de $N$ pasos. Entonces $S_N = S_{target}$. Del paso 4, sabes que $S_N \equiv S_0 \pmod 2$. Esto implica que $S_{target} \equiv S_0 \pmod 2$, lo cual contradice la suposición de que las paridades son diferentes.

   Por lo tanto, el estado objetivo es inalcanzable.

$\square$