Coloraciones en competencias Iberoamericanas

Bipartición y ciclos impares: la herramienta central

El Capítulo 1 estableció el Teorema de Caracterización de Grafos Bipartitos: $G$ es bipartito si y solo si no contiene ciclos de longitud impar. En esta lección aprovechamos este teorema como motor de argumentos olímpicos.

La técnica de 2-coloración tiene dos modos de uso en olimpiadas:

Modo constructivo: Dada una condición de compatibilidad entre objetos, construir la bipartición explícita y demostrar que satisface la condición pedida. Aquí el teorema se usa en la dirección "bipartito $\Rightarrow$ existe 2-coloración".

Modo destructivo: Demostrar que algo es imposible exhibiendo un ciclo impar en el grafo de incompatibilidades. Aquí el teorema se usa en "ciclo impar $\Rightarrow$ no es bipartito $\Rightarrow$ no existe 2-coloración válida".

La coloración de tableros de ajedrez (casilleros blancos y negros) es el ejemplo paradigmático del modo constructivo: la bipartición blanco/negro es la 2-coloración explícita del grafo de adyacencia del tablero, y sirve para argumentos de paridad, de imposibilidad de recubrimientos y de invariantes en procesos.

Invariante de coloración: Una de las aplicaciones más potentes en olimpiadas es usar la coloración como un invariante en un proceso iterativo. Si cada paso del proceso conserva la paridad de la coloración (o si cada movimiento alterna colores), la coloración es un invariante que restringe los estados accesibles.

Coloración de tableros y el truco de la bipartición

El tablero $m \times n$ de ajedrez define un grafo bipartito $G$: los vértices son los $mn$ casilleros y dos casilleros son adyacentes si comparten un lado. La bipartición es la coloración blanco/negro estándar: los casilleros $(i,j)$ con $i+j$ par son blancos (clase $A$) y los con $i+j$ impar son negros (clase $B$).

Invariante de paridad para el caballo: Un caballo en el ajedrez se mueve siempre a un casillero del color opuesto (de blanco a negro y viceversa). Esto significa que la paridad del color cambia en cada movimiento. Consecuencia: si el caballo comienza en un casillero blanco, después de un número impar de movimientos está en un casillero negro, y después de un número par de movimientos está en un casillero blanco. Esto resuelve problemas del tipo "¿puede el caballo hacer un recorrido de $k$ movimientos y volver al inicio si $k$ es impar?".

Imposibilidad de recubrimiento por dominós: Un dominó $1 \times 2$ cubre exactamente un casillero blanco y uno negro. Un recubrimiento perfecto del tablero por dominós corresponde a un matching perfecto en $G$. Si $|A| \neq |B|$ (el número de blancos y negros no es igual), no puede existir un matching perfecto. Este es el argumento para el tablero $8 \times 8$ mutilado (con dos esquinas del mismo color removidas): quedan 30 blancos y 32 negros, imposible cubrir con dominós.

Recubrimiento por triominós en L: Un triominó en L cubre exactamente 3 casilleros. El tablero $2^k \times 2^k$ tiene $4^k$ casilleros: $2^{2k-1}$ blancos y $2^{2k-1}$ negros. Un triominó en L puede cubrir 2 de un color y 1 del otro (hay cuatro orientaciones, dos cubren 2 blancos y 1 negro, dos cubren 1 blanco y 2 negros). La paridad no da una imposibilidad directa, pero la demostración de posibilidad es el argumento inductivo clásico.

2-coloración en tableros no cuadrados: El tablero $m \times n$ tiene $\lceil mn/2 \rceil$ casilleros de un color y $\lfloor mn/2 \rfloor$ del otro. Si $mn$ es par, los dos colores tienen exactamente $mn/2$ casilleros y el tablero puede recubrirse con dominós. Si $mn$ es impar, los dos colores difieren en 1 y el recubrimiento es imposible. La 2-coloración revela la paridad de $mn$ como el obstáculo fundamental.

Invariantes por coloración de aristas

La coloración no se limita a vértices: la coloración de aristas (asignar colores a las aristas de modo que aristas con un vértice común reciban colores distintos) tiene su propia teoría y sus propias aplicaciones olímpicas.

El índice cromático $\chi'(G)$ es el mínimo número de colores para una coloración propia de aristas. El Teorema de Vizing establece que $\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1$; los grafos con $\chi'(G) = \Delta$ se llaman "Clase 1" y los con $\chi'(G) = \Delta + 1$ se llaman "Clase 2". Los grafos bipartitos son siempre Clase 1 (Teorema de König para coloración de aristas).

Coloración de aristas como invariante: En un proceso donde se añaden o eliminan aristas del grafo, la paridad del número de aristas de cada color actúa como un invariante. Si el proceso sólo puede alterar la paridad de un color a la vez, la paridad del número de aristas de un color dado es un invariante módulo 2.

Problema clásico con invariante de coloración: Se tiene un tablero $n \times n$. En cada paso, se elige una fila o una columna y se invierten todos los signos de sus entradas (de $+1$ a $-1$ y viceversa). El tablero comienza con todas las entradas $+1$. ¿Puede obtenerse un tablero con exactamente una entrada $-1$? Solución: coloreamos las filas con dos colores (pares e impares) y observamos que el número de $-1$ en filas pares tiene paridad que cambia por 1 en cada operación de fila par, y el número de $-1$ en filas impares cambia por 1 en cada operación de fila impar. Un análisis de paridades muestra que el número total de $-1$ es siempre par o siempre impar (dependiendo de la paridad de $n$). Para $n$ par, siempre es par; como 1 es impar, es imposible.

Coloración de aristas para problemas de horarios: La coloración propia de aristas de un grafo bipartito $K_{n,n}$ con $n$ colores corresponde a una programación de torneo round-robin: asignar rondas (colores) a partidas (aristas) de modo que ningún equipo juegue dos partidas en la misma ronda. El Teorema de König garantiza que esto siempre es posible con $n$ rondas para $n$ equipos.

Problema Iberoamericano completo: IbAm 2017 P1

Problema (Olimpiada Iberoamericana de Matemáticas 2017, Problema 1): Se tiene un tablero $n \times n$ ($n \geq 2$) con casilleros coloreados como un tablero de ajedrez (blanco y negro, alternados). En cada movimiento se puede elegir un cuadrado $2 \times 2$ del tablero y rotar sus cuatro casilleros $90°$ (ciclando sus contenidos en sentido horario o antihorario). Inicialmente, el tablero tiene los números $1, 2, \ldots, n^2$ colocados de izquierda a derecha, de arriba a abajo. ¿Para qué valores de $n$ es posible, mediante una serie de movimientos, llevar el número 1 a la posición del número 2?

Análisis del movimiento: Un cuadrado $2 \times 2$ tiene sus cuatro casilleros coloreados con 2 blancos y 2 negros (en disposición alternada). Una rotación de $90°$ envía cada casillero a uno del color opuesto. Por tanto, cada movimiento mueve números de casilleros blancos a casilleros negros y viceversa, preservando el número total de números en cada color.

Invariante de coloración: Sea $B$ el conjunto de posiciones blancas y $N$ el de posiciones negras. Cada movimiento es una permutación de los contenidos que envía exactamente 2 valores de $B$ a $N$ y 2 de $N$ a $B$ (los cuatro casilleros del cuadrado $2 \times 2$). Más precisamente: el movimiento realiza el ciclo $(b_1, n_1, b_2, n_2)$ o $(b_1, n_2, b_2, n_1)$ donde $b_1, b_2 \in B$ y $n_1, n_2 \in N$.

Paridad de la permutación: Una rotación de 4 elementos es un 4-ciclo, que es una permutación impar (signo $-1$). Por tanto, cada movimiento es una permutación impar de los $n^2$ casilleros.

Condición necesaria: El número 1 está inicialmente en la posición 1 (blanca si $1+1=2$ par, ¿o negra? Asumimos $(1,1)$ es blanca, luego posición 1 es blanca). El número 2 está en la posición 2 (negra). Para llevar el 1 a donde estaba el 2, la permutación total aplicada debe tener un ciclo específico: al menos mover el 1 de la posición 1 a la posición 2. Cualquier secuencia de $k$ movimientos es una composición de $k$ permutaciones impares, luego tiene signo $(-1)^k$.

La transposición (1,2): La transposición que intercambia el contenido de las posiciones 1 y 2 y deja todo lo demás fijo tiene signo $-1$ (impar). Para lograrla con movimientos (cada uno de signo $-1$), se necesita un número impar de movimientos: $(-1)^k = -1 \Rightarrow k$ impar. Esto es posible en principio.

Condición de paridad de color: La posición 1 es blanca y la posición 2 es negra. Como cada movimiento envía exactamente 2 valores de blanco a negro, la paridad del número de valores blancos que han pasado a negro es siempre par. Luego el número 1 (inicialmente blanco) puede pasar a una posición negra solo si también se mueve otro valor de blanco a negro en ese proceso. Esto es compatible con que el 1 vaya a la posición del 2 (negra).

**Análisis por paridad de $n$:** Cuando $n$ es impar, $n^2$ es impar: hay $(n^2+1)/2$ casilleros de un color y $(n^2-1)/2$ del otro. La posición 1 y la posición 2 tienen colores distintos. El análisis de la permutación total debe ser más cuidadoso. La conclusión (que se demuestra verificando los casos $n=2,3$ y usando el argumento de paridad para general) es: el movimiento es posible si y solo si $n$ es par.

Conclusión: Para $n$ par, la transposición deseada es alcanzable (se puede construir explícitamente una secuencia de movimientos). Para $n$ impar, el invariante de coloración —la paridad del número de valores de cada color en su posición original— impide lograrlo. $\boxed{n \text{ par}}$.

Estrategia integrada: identificar el invariante correcto

La lección más importante de este capítulo es que la coloración es una herramienta para detectar invariantes. Cuando un problema pide demostrar que algo es imposible, o que un estado es inalcanzable, la estrategia es:

Paso 1 — Modelar como grafo: Identificar los estados del problema como vértices de un grafo, y los movimientos/transiciones como aristas o como cambios de estado.

Paso 2 — Colorear el grafo: Asignar colores a los vértices (o a las aristas) según alguna propiedad natural. Las opciones más comunes son: paridad de la posición, paridad de la permutación, signos en una tabla, paridad del número de ciertos objetos.

Paso 3 — Identificar el invariante: Determinar qué propiedad de la coloración se preserva en cada movimiento. Candidatos: la paridad del número de vértices de cada color que han cambiado de estado, la paridad de la permutación total realizada, la suma de los colores (módulo 2 o módulo $k$).

Paso 4 — Derivar la imposibilidad: Si el estado inicial tiene una cierta paridad del invariante y el estado final buscado tiene la paridad opuesta, el proceso es imposible.

Errores comunes: (a) Usar una coloración que no es un verdadero invariante (que cambia de forma no controlada en algunos pasos). (b) Olvidar verificar que el invariante realmente distingue el estado inicial del final. (c) Confundir "el invariante muestra que es imposible" con "el invariante muestra que es posible": la coloración solo da condiciones necesarias, no suficientes, para la posibilidad. Para mostrar posibilidad hay que construir una secuencia explícita de movimientos.

Resumen del Capítulo 2: Las cuatro lecciones cubren coloraciones de grafos ($\chi(G)$, cota greedy, familias clásicas), el Teorema de Brooks ($\chi \leq \Delta$ salvo excepciones), el principio de extremo (camino más largo, objeto más especial, tres problemas olímpicos), y coloraciones en competencias (bipartición, invariantes de tablero, coloración de aristas, problema IbAm completo). Estas herramientas son el núcleo del capítulo de coloraciones en olimpiadas latinoamericanas de nivel 2.