Invariantes Módulo k

Teoría

Los invariantes módulo $k$ son una clase específica de cantidades invariantes que vas a usar principalmente en procesos combinatorios, teoría de juegos algorítmica y problemas de mosaicos. La idea central es que identifiques una propiedad del sistema —que representas como un valor entero— que se mantenga congruente al mismo residuo módulo $k$ después de que hagas cualquier operación válida. Aunque el valor absoluto de la cantidad puede cambiar drásticamente durante el proceso, su clase de residuo módulo $k$ se queda igual. Esta técnica es como un filtro "grueso"; al ignorar la magnitud y enfocarte en la divisibilidad, puedes clasificar los estados alcanzables de un sistema en conjuntos ajenos basados en sus residuos.

Vas a usar esta técnica muy seguido para demostrar resultados de imposibilidad (demostrar que no puedes llegar a un estado objetivo desde un estado inicial) o para analizar cómo se comportan los sistemas dinámicos. Por ejemplo, si un estado inicial tiene un valor invariante de $1 \pmod 3$ y un estado objetivo tiene un valor de $0 \pmod 3$, la transición es imposible sin importar cuántas operaciones hagas o qué tan complejas sean. Esta es una herramienta fundamental en competencias como el AIME y la USAMO, y muchas veces da soluciones elegantes de un solo renglón a problemas que de otra forma requerirían un análisis de casos muy pesado.

La intuición para encontrar un invariante módulo $k$ casi siempre implica que revises el cambio "local" que causa una operación. Si una operación reemplaza