Problemas de existencia: invariantes y semivariantes

Invariantes: definición y clasificación

Un invariante de un proceso combinatorio es una cantidad asociada al estado del sistema que permanece constante a lo largo de todas las transformaciones permitidas. Si el estado inicial $s_0$ y el estado objetivo $s_f$ difieren en el valor del invariante, entonces $s_f$ es inalcanzable desde $s_0$.

Clasificación por tipo:

(a) Invariante aditivo. La suma $\sum f(s_i)$ de alguna función de las piezas permanece constante. Ejemplo: la paridad del número de inversiones en una permutación (invariante de las transposiciones).

(b) Invariante multiplicativo. El producto $\prod g(s_i)$ permanece constante. Ejemplo: el signo de una permutación ($\pm 1$) bajo transposiciones.

(c) Invariante modular. Cierta cantidad permanece constante módulo $m$. Ejemplo: la suma de los elementos de un conjunto módulo $k$ bajo operaciones de suma/resta que preservan la suma mod $k$.

(d) Invariante estructural. Una propiedad cualitativa (ser conexo, ser bipartito, tener cierto ciclo) que se preserva bajo todas las transformaciones. Ejemplo: la paridad de los ciclos de una permutación bajo cierto tipo de producto.

La habilidad de identificar qué invariante usar es la clave; no hay regla universal, pero la práctica con el Shortlist crea el patrón de reconocimiento.

Semivariantes: demostrar no-alcanzabilidad asimétrica

Un semivariante (o monoinvariante) es una cantidad que bajo las transformaciones permitidas solo puede aumentar (semivariante creciente) o solo puede disminuir (semivariante decreciente). Si el estado objetivo $s_f$ tiene un valor del semivariante estrictamente mayor que el estado inicial $s_0$ (o estrictamente menor), y el semivariante es decreciente (resp. creciente), entonces $s_f$ es inalcanzable.

Uso en problemas de proceso. El problema dice: "El proceso consiste en... ¿puede el sistema llegar al estado $X$?". Para demostrar que no puede:

(1) Definir una cantidad $Q(s)$ del estado $s$.

(2) Demostrar que en cada paso del proceso, $Q(s)$ no disminuye (o no aumenta).

(3) Calcular $Q(s_0)$ y $Q(X)$ y mostrar que $Q(X) < Q(s_0)$ (si $Q$ es no-decreciente), imposibilitando la llegada a $X$.

Ejemplo prototípico. Se tiene un conjunto de enteros positivos. La operación permitida: si $a \ge b$ son dos elementos del conjunto, podemos reemplazarlos por $a-b$ y $a+b$. ¿Puede cualquier conjunto alcanzar el estado $\{1, 2, \ldots, n\}$ partiendo de $\{1, 1, \ldots, 1\}$? El semivariante: la suma de los cuadrados. Tras la operación: $(a-b)^2 + (a+b)^2 = 2a^2 + 2b^2 \ge a^2 + b^2$ (con igualdad solo si $b = 0$). La suma de cuadrados no decrece. Si la suma de cuadrados del objetivo es menor que la del inicio, el objetivo es inalcanzable.

Invariantes en problemas de transformaciones de conjuntos

Un tipo frecuente en IMO Shortlist: se tiene un conjunto finito $S$ y se aplican transformaciones de la forma "reemplaza $x$ por $f(x)$" o "intercambia $x$ e $y$ si satisfacen cierta condición". El problema pide determinar qué estados son alcanzables desde el estado inicial.

El método de orbit-stabilizer combinatorio. Para procesos en conjuntos finitos, la órbita del estado inicial (el conjunto de todos los estados alcanzables) puede ser calculada en casos pequeños. Si la órbita es pequeña, el problema se resuelve por caso; si es grande, se necesita un invariante para delimitar la órbita.

Ejemplo (ISL 2007 C4). Se tienen $n$ fichas en los vértices de un polígono regular. La operación: elige un vértice con $\ge 2$ fichas, toma 2 y coloca 1 en cada uno de los dos vértices adyacentes. ¿Qué configuraciones son alcanzables desde una configuración inicial dada? El invariante: el vector de fichas módulo 2 evoluciona de manera determinista bajo la operación (módulo 2, colocar una ficha en cada vecino corresponde a sumar 1 mod 2 a cada vecino). Esto conecta el problema con el álgebra lineal sobre $\mathbb{F}_2$.

La técnica del "potencial ponderado". Se asigna un peso $w_i > 0$ a la posición $i$ y se considera $\Phi = \sum_i w_i \cdot \text{(número de fichas en } i)$. Se elige $w$ de manera que $\Phi$ sea un invariante o semivariante de la operación. Si los pesos satisfacen $w_i = w_{i-1} + w_{i+1}$ (ecuación de harmónico), la operación preserva $\Phi$. Los pesos harmónicos en polígonos regulares son las funciones propias del laplaciano discreto, conectando con el análisis espectral de grafos (Capítulo 3).

Invariantes modulares y p-ádicos

**Invariante módulo $m$.** La cantidad $Q(s) \bmod m$ es un invariante iff para todo paso del proceso que transforma $s \to s'$, $Q(s) \equiv Q(s') \pmod{m}$. Si $Q(s_0) \not\equiv Q(s_f) \pmod{m}$, entonces $s_f$ es inalcanzable.

Chequeo modular múltiple. Si $m_1, m_2, \ldots, m_k$ son distintos módulos, el estado $s_f$ es inalcanzable si $Q(s_0) \not\equiv Q(s_f) \pmod{m_i}$ para algún $i$. El producto $m_1 m_2 \cdots m_k$ da una condición más fina. En casos avanzados, la condición de alcanzabilidad es exactamente $Q(s_0) \equiv Q(s_f) \pmod{m}$ para algún $m$ que resume toda la información del invariante.

Invariantes 2-ádicos. La valuación 2-ádica $v_2(n)$ (el exponente máximo de $2$ en $n$) es un invariante o semivariante en muchas operaciones que involucran paridades. Si la operación multiplica por 2 en ciertas circunstancias pero nunca divide, $v_2$ es un semivariante creciente. Esto es equivalente a un argumento de paridad iterado.

Ejemplo (IMO 2011/2). Sean $a_1, a_2, \ldots$ una secuencia de enteros positivos. Para cada $n \ge 1$, se denota $s_n = a_1 + \cdots + a_n$. Ningún $s_n$ es divisible por $n^2$... (La resolución usa el invariante de la secuencia módulo ciertos primos, combinado con argumentos de mínimo.)

El invariante como "certificado de imposibilidad". En olimpiadas, la presentación estándar de un argumento de invariante es: (1) Definir $Q$. (2) Demostrar el lema de invarianza: $Q(s) = Q(s')$ para todo paso $s \to s'$. (3) Calcular $Q(s_0) \ne Q(s_f)$. (4) Concluir por contradicción. Cada uno de estos pasos debe ser explícito en la solución olímpica.

Semivariantes en competición: diseño y aplicación

Diseñar el semivariante correcto es un arte. Las heurísticas más útiles en el nivel IMO:

Heurística 1: usar la suma de potencias. Si la operación reemplaza $a, b$ por $f(a, b), g(a, b)$, calcula $p^k + q^k$ para $\{p,q\} = \{f(a,b), g(a,b)\}$ y compáralo con $a^k + b^k$. La diferencia da la monotonicidad del semivariante.

Heurística 2: usar la entropía combinatoria. La función $Q = \sum_i \log(s_i)$ o $Q = \prod_i s_i$ a menudo tiene monotonicidad favorable bajo operaciones de promediado.

Heurística 3: buscar la cantidad mínima. Si la operación siempre reduce la cantidad $\min_i s_i$, esa cantidad es un semivariante decreciente. Esto es suficiente para mostrar que el proceso termina (si el mínimo baja y es entero positivo, el proceso termina en tiempo finito).

Ejemplo (ISL 2014 C6-nivel). Se tiene un multiconjunto de enteros positivos. La operación: elige $a > b$, reemplaza por $(a+b)/2$ y $(a-b)/2$ si ambos son enteros. La cantidad $\max - \min$ del multiconjunto es un semivariante decreciente: $\max(\frac{a+b}{2}, \frac{a-b}{2}) = \frac{a+b}{2} < a$ y $\min \ge \frac{a-b}{2} > 0$. Luego el proceso converge, y el estado límite puede determinarse con el invariante de la suma total.

Presentación en competición. Al demostrar que un proceso termina usando un semivariante, la solución debe: (1) Definir el semivariante $Q$. (2) Demostrar que $Q$ es entero no negativo (o tiene rango discreto). (3) Demostrar que $Q$ estrictamente decrece en cada paso. (4) Concluir que el proceso termina en a lo sumo $Q(s_0)$ pasos.