Usar propiedades par/impar que se mantienen constantes.
Los invariantes de paridad son de las herramientas más fundamentales y poderosas en la optimización combinatoria y en las demostraciones de imposibilidad. En el fondo, un argumento de paridad usa las propiedades de los enteros módulo 2. Un invariante es una propiedad de un sistema que no cambia después de aplicar ciertas operaciones permitidas. En el contexto de la paridad, buscas un valor asociado al estado de un sistema —como la suma de los elementos, el número de inversiones en una permutación o el color de una casilla en una cuadrícula— que se mantenga estrictamente par o estrictamente impar durante todo un proceso. Si el estado inicial tiene paridad par y el estado objetivo tiene paridad impar (o al revés), la transformación es imposible.
Esta técnica es súper importante porque reduce espacios de estados complejos, a veces infinitos, a una simple revisión binaria. La puedes usar seguido para resolver problemas de cubrimiento (como dominós en un tablero de ajedrez), teoría de juegos (estrategias ganadoras) y operaciones algorítmicas (ordenar o transformar conjuntos). El truco clave suele ser definir una función de "valuación" $f(S)$ para un estado $S$ tal que $f(S') \equiv f(S) \pmod 2$ para cualquier estado $S'$ al que puedas llegar desde $S$ en un paso. Otra opción es buscar un invariante alternante donde la paridad cambie con cada movimiento, lo cual sirve para