Problemas de coloración y partición

Taxonomía de los problemas de coloración IMO

Los problemas de coloración y partición en el IMO y el IMO Shortlist (categoría C) pueden clasificarse en cuatro subtipos según el tipo de garantía que buscan:

(I) Existencia monócroma: dada una coloración de un conjunto estructurado, demostrar que existe una subestructura monocrómatica (un subconjunto, una progresión, un subgrafo) de un tipo específico. Herramientas: Ramsey, van der Waerden, Hales-Jewett.

(II) Construcción óptima: demostrar que existe una coloración con cierta propiedad (o que no existe), usualmente la que maximiza o minimiza una cantidad. Herramientas: doble conteo, construcciones probabilísticas, argumentos de compacidad.

(III) Partición con restricciones: demostrar que un conjunto puede (o no puede) partirse en partes que satisfacen condiciones dadas. Herramientas: invariantes, argumentos de paridad, coloración de tableros.

(IV) Coloración de grafos: demostrar que cierto grafo es $k$-coloreable, o hallar el número cromático, en el contexto de un problema estructural más amplio. Herramientas: grafos perfectos, lema de Hajós, argumento greedy con lema de degeneración.

La identificación del subtipo en los primeros tres minutos de lectura es la competencia central del candidato IMO. Los subtipos I y III son los más frecuentes en C1–C5 del Shortlist.

El principio de Pigeonhole cuantitativo

La forma elemental ("si $n+1$ objetos se distribuyen en $n$ cajas, alguna caja tiene $\ge 2$") debe dominarse en su versión cuantitativa para el IMO:

Teorema (Pigeonhole cuantitativo). Si $n$ objetos se distribuyen en $k$ cajas, alguna caja contiene al menos $\lceil n/k \rceil$ objetos. Más precisamente, si la distribución da $a_1, \ldots, a_k$ objetos con $\sum a_i = n$, entonces $\max_i a_i \ge \lceil n/k \rceil$.

Forma dual (palomar inverso). Si $n$ objetos se distribuyen en $k$ cajas y cada caja contiene al menos $m$ objetos, entonces $n \ge km$. Contrapositivo: si $n < km$, alguna caja tiene menos de $m$ objetos.

Pigeonhole iterado. Dada una coloración $c: \{1, \ldots, N\} \to [k]$, existe un color $j$ tal que $|c^{-1}(j)| \ge N/k$. El conjunto $c^{-1}(j)$ hereda la estructura aritmética de $\{1, \ldots, N\}$; los resultados de densidad (Szemerédi, Green-Tao) son extensiones profundas de esta idea.

Ejemplo IMO-nivel. En una cuadrícula $n \times n$, se colocan $n^2 + 1$ fichas (no necesariamente distintas) en las casillas. Entonces existe una fila con al menos $n + 1$ fichas (por Pigeonhole en las $n$ filas). Aplicar luego Pigeonhole en las columnas de esa fila da una casilla con $\ge 2$ fichas. Este doble Pigeonhole es la estructura básica de muchos problemas C1.

Coloraciones y progresiones: van der Waerden

Teorema de van der Waerden (1927). Para todo $r \ge 1$ y $k \ge 1$, existe $W(r, k)$ tal que toda $r$-coloración de $\{1, \ldots, W(r,k)\}$ contiene una progresión aritmética monocrómatica de longitud $k$.

Uso en IMO. Van der Waerden aparece en problemas que piden demostrar que cierta estructura monocrómatica existe para cualquier coloración, o que preguntan por los valores mínimos de $N$ para los cuales toda coloración de $\{1, \ldots, N\}$ garantiza cierto objeto. La demostración de van der Waerden usa un argumento de doble inducción (en $r$ y $k$) que es modelo de demostración en olimpiadas.

**Demostración esquemática ($r = 2$, $k = 3$).** Sea $N = W(2,3)$. Queremos: en toda 2-coloración de $\{1, \ldots, N\}$, hay una PA monocrómatica de longitud 3. El argumento: primero demos que $W(2,2) = 3$ (trivialmente, en cualquier 2-coloración de $\{1,2,3\}$ hay una PA de longitud 2). Luego, usando el primer nivel como base, se construye $N$ suficientemente grande para forzar una PA de longitud 3 en uno de los dos colores. El argumento central: si $\{a, a+d, a+2d\}$ no es monocrómático para el color rojo, entonces hay restricciones en la coloración de $\{a, a+d, a+2d\}$ que fuerzan una PA en azul.

**Partición de $\mathbb{Z}$ en dos conjuntos libres de PA.** A diferencia de van der Waerden, una sola parte de $\mathbb{Z}$ puede ser libre de progresiones aritméticas de longitud 3 (ejemplo: el conjunto de Behrend). Sin embargo, ninguna 2-coloración de $\mathbb{Z}_{\ge 1}$ puede hacer que ambas partes sean libres de PA de longitud 3. Esta asimetría es la esencia de van der Waerden.

La técnica de la coloración certificado

En problemas de partición del tipo "demuestra que no existe partición de $S$ en partes $A$ y $B$ con la propiedad $P$", la herramienta estándar es encontrar un certificado combinatorio: un objeto en $S$ cuya estructura obliga a contradicciones en cualquier partición que intente satisfacer $P$.

Coloración de tablero. Un problema clásico: ¿puede un tablero $m \times n$ con algunas casillas eliminadas cubrirse perfectamente con dominos ($1 \times 2$)? La coloración de ajedrez (cada casilla coloreada blanco o negro alternadamente) da el certificado: un cubrimiento perfecto requiere que el tablero tenga igual número de casillas blancas y negras. Si la cantidad de blancas y negras difiere, el cubrimiento es imposible. La coloración actúa como invariante de la partición.

Invariante de coloración para particiones. Dado un conjunto $S$ y una propiedad $P$ de particiones $S = A \cup B$, se busca una función $f: S \to \mathbb{Z}$ tal que cualquier partición con $P$ satisface $\sum_{s \in A} f(s) = \sum_{s \in B} f(s)$ (o alguna relación similar). Si se puede calcular que ninguna partición cumple esta relación, $P$ es imposible.

Ejemplo (ISL 2011 C3-nivel). Se tiene un conjunto $S$ de $2n$ enteros. ¿Puede $S$ partirse en dos subconjuntos $A$, $B$ de tamaño $n$ tales que $\sum_{a \in A} a = \sum_{b \in B} b$? El certificado: la suma total $\sigma = \sum_{s \in S} s$ debe ser par (pues $2\sum_{a \in A} a = \sigma$). Si $\sigma$ es impar, la partición es imposible. Si $\sigma$ es par, la existencia depende de la estructura de $S$ (no es automática).

Coloraciones multicromáticas. Para propiedades más complejas (partición en $k \ge 3$ partes), la coloración certificado se generaliza a una función $f: S \to \mathbb{Z}/k\mathbb{Z}$ o $f: S \to \mathbb{F}_p$. Los argumentos de álgebra lineal sobre $\mathbb{F}_2$ (Capítulo 3) son el caso más rico de esta técnica en el nivel IMO.

Particiones y el principio de extremos

En muchos problemas IMO de partición, la estrategia ganadora es considerar el elemento extremal de una parte: el máximo, el mínimo, o el elemento con máxima suma de vecinos, y derivar contradicciones o invariantes desde allí.

Principio del extremo en coloraciones de grafos. Dado un grafo $G$ con coloración propia de $k$ colores, el vértice con mayor grado en una clase de color tiene propiedades especiales. Si el grado máximo de $G$ es $\Delta$, entonces $G$ es $(\Delta+1)$-coloreable (por greedy), y es $\Delta$-coloreable a menos que $G$ tenga una componente completa o un ciclo impar (Teorema de Brooks).

Aplicación IMO directa. Un problema pide: demuestra que los vértices de un grafo $G$ pueden partirse en dos conjuntos $A$ y $B$ tal que cada vértice de $A$ tiene al menos la mitad de sus vecinos en $B$, y viceversa. Argumento del extremo: considera la partición $A, B$ que maximiza el número de aristas entre $A$ y $B$ (aristas de corte). En esta partición óptima, si algún vértice $v \in A$ tuviera más vecinos en $A$ que en $B$, moverlo a $B$ aumentaría el número de aristas de corte, contradiciendo la maximalidad. Luego en la partición óptima, cada vértice tiene al menos la mitad de sus vecinos en la parte contraria.

Este argumento, llamado "Max-cut via greedy" o "argumento de bisección local", es uno de los más versátiles en problemas IMO C2–C4. La partición que maximiza las aristas de corte existe (hay finitas particiones) y satisface la propiedad deseada.