Cuando la suma de las paridades no cambia.
La paridad es una de las herramientas más poderosas en combinatoria y teoría de números. Muchas veces, la clave de un problema no es el valor exacto de una suma, sino si esa suma es par o impar.
Seguro ya conoces las reglas básicas para sumar y multiplicar números pares e impares:
Un truco común es fijarse en la suma total de un conjunto de números de dos formas distintas. Si una forma te dice que la suma debe ser par y la otra te dice que debe ser impar, ¡encontraste una contradicción!
Imagina un grafo donde cada vértice representa a una persona y una arista representa un apretón de manos. Cada arista conecta a dos personas, así que cada apretón de manos aporta exactamente 2 a la suma de los grados de todos los vértices:
$$\sum_{v \in V} \text{deg}(v) = 2|E|$$
Como $2|E|$ siempre es par, la suma de los grados tiene que ser par. Esto nos lleva al famoso Handshaking Lemma: en cualquier grafo, el número de vértices con grado impar tiene que ser par.
En muchos problemas de procesos, te preguntan si puedes llegar a cierto estado desde un estado inicial. La paridad suele ser un invariante, o sea, algo que no cambia.
Supón que tienes los números $1, 2, \dots, 10$ en un pizarrón. En cada paso, eliges dos números $a$ y $b$, los borras y escribes $|a-b|$. ¿Puedes terminar con el número 0?
Fíjate en la suma $S = \sum a_i$. Cuando cambias $a$ y $b$ por $|a-b|$, la suma pasa de $S$ a $S - a - b + |a-b|$. Nota que $a+b$ y $|a-b|$ siempre tienen la misma paridad porque $(a+b) - (a-b) = 2b$, que es par. ¡Así que la paridad de la suma total nunca cambia!
La suma inicial es $1+2+\dots+10 = 55$, que es impar. Como la paridad es un invariante, el número final también tiene que ser impar. Pero el 0 es par, así que es imposible.