Monovariantes

Teoría

Una monovariante es una cantidad asociada al estado de un sistema que cambia de forma monótona (ya sea que siempre aumenta o siempre disminuye) cada vez que haces una operación específica. A diferencia de las invariantes, que se quedan constantes durante todo un proceso, las monovariantes son herramientas dinámicas que usas principalmente para analizar procesos algorítmicos, juegos o transformaciones. Son súper útiles para demostrar que un proceso tiene que terminar tarde o temprano o estabilizarse en un ciclo, en lugar de seguir para siempre o volverse un caos.

La intuición básica detrás de las monovariantes depende de que el espacio de estados sea finito. Si un sistema tiene un número finito de configuraciones posibles, y un valor definido asociado al sistema aumenta estrictamente en cada paso, el proceso no puede durar para siempre. Eventualmente tiene que llegar a un estado donde ya no puedas hacer más operaciones (un máximo local) o entrar en un ciclo específico. Este concepto es parecido a la energía potencial en física: una pelota que rueda hacia abajo en una colina (perdiendo energía potencial) tiene que detenerse en un mínimo si la colina es finita y hay fricción.

En las olimpiadas de matemáticas, encontrar la monovariante correcta suele ser la clave para resolver problemas de combinatoria difíciles. La dificultad no está en las cuentas, sino en construir una función ingeniosa —como una suma de cuadrados, un conteo de inversiones o una suma con pesos específicos— que mida el "progreso" del sistema. Esta técnica se usa mucho en teoría de gráficas (por ejemplo, para partir gráficas), teoría de números (como en sucesiones de operaciones con enteros) y problemas de pavimentación para demostrar que algo se puede alcanzar o que un proceso termina.

Fórmulas Clave

Aunque las monovariantes son funciones que tú mismo defines según el problema y no fórmulas fijas, la técnica se basa en estos principios estructurales.

1. Definición de una monovariante Sea $S$ el conjunto de todos los estados posibles de un sistema. Una función $M: S \to \mathbb{R}$ es una monovariante respecto a una transición $T: S \to S$ si para todos los estados válidos $s_i$: $$ M(T(s_i)) > M(s_i) \quad \text{(Estrictamente creciente)} $$ o $$ M(T(s_i)) < M(s_i) \quad \text{(Estrictamente decreciente)} $$

2. El principio de terminación Si un proceso genera una sucesión de estados $s_0, s_1, s_2, \dots$ tal que $M(s_{i+1}) > M(s_i)$ para toda $i$, y el conjunto de valores posibles para $M$ está acotado superiormente (o el conjunto de estados es finito), entonces la sucesión tiene que ser finita. El proceso termina en algún estado $s_n$.

3. Construcciones comunes de monovariantes Cuando estés buscando una monovariante, estas construcciones suelen funcionar:

• Sumas de cuadrados: $$ M = \sum_{i=1}^n x_i^2 $$ (Útil cuando los valores se acercan o se alejan entre sí).
• Distancia al objetivo: $$ M = \sum |x_i - t_i| $$
• Orden lexicográfico: Tratar el estado como un vector y checar si el vector aumenta lexicográficamente.
• Inversiones: En problemas de permutaciones, contar parejas $(i, j)$ tales que $i < j$ pero $a_i > a_j$.
• Tamaño del corte de una gráfica: $$ M = |E(A, B)| $$ (El número de aristas que conectan dos conjuntos ajenos de vértices).

Demostración

Teorema (La partición amistosa): Dada una gráfica finita $G = (V, E)$, siempre es posible partir los vértices en dos conjuntos ajenos $A$ y $B$ (donde $V = A \cup B$ y $A \cap B = \emptyset$) de tal forma que cada vértice $v$ tenga al menos la mitad de sus vecinos en el conjunto opuesto al que contiene a $v$.

Demostración:

Paso 1: Define el espacio de estados Toma cualquier partición de los vértices $V$ en dos conjuntos $A$ y $B$ como un estado. Como $V$ es finito, hay $2^{|V|}$ particiones posibles (un número finito).

Paso 2: Define la monovariante Sea $M(A, B)$ el número de aristas que conectan un vértice en el conjunto $A$ con un vértice en el conjunto $B$. A estas las llamamos "aristas de corte". $$ M(A, B) = |{ {u, v} \in E \mid u \in A, v \in B }| $$

Paso 3: Define la operación Decimos que un vértice $v$ es "infeliz" si no cumple la condición del teorema. Es decir, $v$ tiene más vecinos en su propio conjunto que en el conjunto opuesto. Sea $d(v)$ el grado de $v$. Sea $d_{int}(v)$ el número de vecinos en el mismo conjunto que $v$, y $d_{ext}(v)$ el número de vecinos en el conjunto opuesto. Un vértice es infeliz si $d_{int}(v) > d_{ext}(v)$ (lo que implica que $d_{int}(v) > \frac{1}{2}d(v)$).

La operación es: Si un vértice $v$ es infeliz, muévelo al otro conjunto.

Paso 4: Analiza el cambio en la monovariante Supón que $v \in A$ es infeliz. Esto significa que $v$ tiene más vecinos en $A$ que en $B$. Mueve $v$ de $A$ a $B$ para crear una nueva partición $(A', B')$. Analiza cómo cambia el número de aristas de corte $M$:

1. Las aristas que conectan a $v$ con sus vecinos en $A$ antes eran internas; ahora conectan $A'$ con $B'$ (se vuelven aristas de corte). Hay $d_{int}(v)$ de estas aristas.
2. Las aristas que conectan a $v$ con sus vecinos en $B$ antes eran aristas de corte; ahora conectan vértices dentro de $B'$ (se vuelven aristas internas). Hay $d_{ext}(v)$ de estas aristas.

El nuevo valor de la monovariante es: $$ M(A', B') = M(A, B) + d_{int}(v) - d_{ext}(v) $$

Como $v$ era infeliz, sabes que $d_{int}(v) > d_{ext}(v)$. Por lo tanto: $$ d_{int}(v) - d_{ext}(v) \geq 1 $$ $$ M(A', B') > M(A, B) $$

Paso 5: Conclusión por terminación Cada vez que mueves un vértice infeliz, el número de aristas de corte aumenta estrictamente. El número máximo posible de aristas de corte es el número total de aristas $|E|$, que es finito. Por lo tanto, la secuencia de operaciones no puede seguir para siempre. El proceso tiene que terminar en un estado donde la monovariante ya no pueda aumentar más. En este estado final, no hay vértices infelices (si los hubiera, podrías mover uno y aumentar $M$). Así que cada vértice tiene que cumplir que $d_{ext}(v) \geq d_{int}(v)$, lo que demuestra que la partición existe.

$\square$