Aplicaciones olímpicas: cómo reconocer Ramsey en concursos

Taxonomía de los disfraces de Ramsey en competencias

El Teorema de Ramsey y sus parientes aparecen en olimpiadas bajo al menos seis disfraces diferentes, cada uno con sus peculiaridades de presentación. Aprender a reconocerlos es la primera habilidad que distingue al resolutor experto del principiante.

Disfraz 1: El problema de amistad/enemistad. "En un grupo de $n$ personas, cada par es amigo o enemigo. Demuestra que existe un grupo de $k$ personas con relación homogénea." Traducción directa: coloración de aristas de $K_n$, busca $K_k$ monocromático, aplica $R(k,k) \le n$.

Disfraz 2: El problema de torneo. "En un torneo donde todo par de equipos juega exactamente una vez, demuestra que existen $k$ equipos con un cierto patrón de resultados." La orientación de aristas del grafo completo es equivalente a una 2-coloración (ganó/perdió). Un triángulo transitivo (los tres se ganan en cadena) versus un triángulo cíclico (ciclo $A \to B \to C \to A$) son los dos tipos de triángulo en $K_3$ dirigido.

Disfraz 3: El problema de colores en el plano. "Los enteros o los puntos del plano se colorean con $r$ colores. Demuestra que existen tres puntos del mismo color que forman un triángulo con cierta propiedad (isósceles, equilátero, con cierta distancia)." Aquí se combina Ramsey con geometría: la estructura del espacio impone restricciones sobre qué triángulos son posibles, y el argumento probabilístico o de paloma establece la inevitabilidad.

Disfraz 4: El problema de partición de enteros. "Los enteros $\{1, \ldots, n\}$ se particionan en $k$ clases. Demuestra que alguna clase contiene $x, y, z$ con $x + y = z$ (o $xy = z^2$, o $x,y,z$ en progresión aritmética, etc.)." Estos son los Teoremas de Schur, Van der Waerden y sus variantes algebraicas.

Disfraz 5: El problema de hipergrafos. "Tienes $n$ conjuntos de $k$ elementos cada uno. Demuestra que existen $m$ conjuntos con intersección vacía pairwise (o intersección no vacía, o contenidos uno en otro)." El grafo de intersección o la $k$-coloración de sistemas de conjuntos suelen ser el modelo correcto.

Disfraz 6: El problema de juego estratégico. "Dos jugadores colorean aristas de $K_n$ una a una. El primero que completa un $K_k$ monocromático en su color gana. ¿Para qué $n$ tiene el primer jugador estrategia ganadora?" Esto es el juego de Ramsey, donde se combina la teoría con argumentos de estrategia robada.

Estrategia unificada: el esquema de solución en 5 pasos

Para cualquier problema de tipo Ramsey, el proceso de solución óptimo en competencia sigue estos cinco pasos, que en la práctica se ejecutan en paralelo con el pensamiento pero que conviene articular explícitamente cuando se está aprendiendo.

Paso 1: Modelado. Identifica los "objetos" (vértices) y las "relaciones" (aristas con colores). Determina si el grafo es completo, bipartito, regular, o tiene otra estructura. Escribe explícitamente: "Sea $G$ el grafo con vértices $V = \{\ldots\}$ y aristas coloreadas con los colores $\{\ldots\}$ donde $\{u,v\}$ tiene color $c$ si [condición]."

Paso 2: Identificación del target. Determina qué estructura monocromática buscas. ¿Un $K_k$? ¿Una progresión aritmética de longitud $k$? ¿Un árbol específico? Escribe: "Queremos demostrar la existencia de [estructura] completamente en el color [color] para algún [color]." Si el problema pide una cota inferior (construir coloración sin la estructura), el paso 2 es identificar la estructura que quieres evitar.

Paso 3: Selección del argumento. Para cotas superiores (inevitabilidad): (a) argumento de paloma en un vértice (más común), (b) conteo de estructuras monocromáticas (útil cuando hay muchos colores o la estructura no es $K_k$), (c) inducción con recurrencia (cuando $k$ es variable). Para cotas inferiores (construcciones): (a) grafo circulante, (b) producto de grafos, (c) construcción algebraica sobre $\mathbb{F}_q$.

Paso 4: Ejecución. Escribe la demostración limpiamente. Para paloma: "Sea $v$ un vértice. Sus $n-1$ aristas se distribuyen en $r$ colores; por paloma, al menos $\lceil (n-1)/r \rceil$ aristas tienen el mismo color $c$. Sea $N_c$ el conjunto de esos vecinos. Por hipótesis inductiva aplicada a $K_{|N_c|}$..." Para construcción: "Definimos la coloración $\chi: E(K_n) \to [r]$ por $\chi(\{i,j\}) = f(i-j \bmod n)$ donde $f: \mathbb{Z}_n \to [r]$ se define por [tabla/fórmula]. Verificamos que no hay $K_k$ monocromático: [verificación]."

Paso 5: Verificación de los casos base y la condición numérica. En competencias, la aritmética de "¿qué valor de $n$ es suficiente?" es donde se pierden muchos puntos. Verifica explícitamente que el $n$ que usas cumple las desigualdades del argumento de paloma, y que tu construcción extremal realmente funciona para $n-1$. Un error de $\pm 1$ en el umbral puede invalidar toda la solución.

Análisis detallado: IMO 2007 Problema 3

El IMO 2007 Problema 3 es uno de los más elegantes de la historia reciente en combinatoria. Enunciado: "En un club matemático, algunas parejas de miembros son amigos. Se sabe que toda pareja de amigos tiene exactamente un amigo en común. Demuestra que hay un miembro que es amigo de todos los demás miembros del club."

Este problema parece Ramsey pero en realidad es un teorema de amistad (Friendship Theorem). Sin embargo, el análisis requiere técnicas que también aparecen en Ramsey. La condición "toda pareja de amigos tiene exactamente un amigo en común" significa que el grafo $G$ es tal que para toda arista $\{u,v\}$, hay exactamente un vértice $w$ adyacente tanto a $u$ como a $v$: el grafo no tiene 4-ciclos ($C_4$) como subgrafo, y más aún, cualquier dos vecinos de un vértice tienen exactamente un vecino en común.

La demostración clásica usa álgebra lineal: sea $A$ la matriz de adyacencia de $G$. La condición se traduce en $(A^2)_{ij} = 1$ para $i \ne j$ y $(A^2)_{ii} = \deg(i)$. Esto implica $A^2 = (D-I) + J$ donde $D$ es la matriz diagonal de grados, $I$ la identidad y $J$ la matriz de todos-unos. Si todos los grados son iguales a $k$ (caso regular), $A^2 = (k-1)I + J$. Los valores propios de $J$ son $n$ (con vector propio $(1,\ldots,1)/\sqrt{n}$) y $0$ (con multiplicidad $n-1$). Los valores propios de $A^2$ son entonces $k-1+n$ y $k-1$, así los de $A$ son $\pm\sqrt{k-1+n}$ y $\pm\sqrt{k-1}$.

La traza de $A$ es $0$ (no hay lazos), lo que implica que los valores propios suman $0$. Con las multiplicidades apropiadas, se obtiene una ecuación diofántica en $k$ y $n$ que solo tiene soluciones cuando $k$ divide a $n-1$ y $k$ es la solución de un sistema cuadrático. Resolviendo: $k = n-1$ (el vértice "amigo universal") o $k^2 = n-1$ (que lleva a contradicción con el resto del argumento). El caso irregular requiere un argumento diferente para mostrar que no puede ocurrir.

Relevancia para Ramsey: la técnica de la matriz de adyacencia y los valores propios es exactamente la herramienta de la "combinatoria algebraica espectral" que también se usa para demostrar cotas de Ramsey en grafos con estructura algebraica. El espectro de Cayley de un grupo abeliano determina si el grafo de Cayley asociado es una buena coloración de Ramsey. Esta conexión entre espectro y combinatoria extremal es el tema del Capítulo 4 de este módulo.

Análisis detallado: IMO Shortlist 2011 C4

IMO Shortlist 2011 C4: "En cada celda de una tabla $n \times n$ se escribe un entero no negativo. Se sabe que la suma de todos los enteros de la tabla es $S$. Demuestra que existe una fila o columna cuya suma es al menos $S/n$." Este es un resultado elemental de promedio, pero el Shortlist 2011 C4 real es: "Sea $n$ enteros positivos distintos $a_1, \ldots, a_n$. Para cada par $(i,j)$, coloreamos la celda $(i,j)$ de rojo si $a_i + a_j$ es par, y de azul si $a_i + a_j$ es impar. Demuestra que el número de celdas rojas es estrictamente mayor que el número de celdas azules si y solo si más de $n/2$ de los $a_i$ tienen la misma paridad."

Solución: Sea $r$ el número de los $a_i$ pares y $s = n - r$ el número de los impares. Una celda $(i,j)$ con $i < j$ es roja si $a_i + a_j$ es par (ambos pares o ambos impares) y azul si $a_i + a_j$ es impar. El número de celdas rojas es $\binom{r}{2} + \binom{s}{2}$ y el de azules es $r \cdot s$. La condición "rojas $>$ azules" equivale a $\binom{r}{2} + \binom{s}{2} > rs$, es decir $r(r-1)/2 + s(s-1)/2 > rs$. Simplificando: $r^2 - r + s^2 - s > 2rs$, lo que da $(r-s)^2 > r+s = n$. Esto equivale a $|r-s| > \sqrt{n}$, que ocurre si y solo si $r > n/2 + \sqrt{n}/2$ o $s > n/2 + \sqrt{n}/2$... pero la condición pedida es "más de $n/2$ tienen la misma paridad", es decir $\max(r,s) > n/2$.

La equivalencia exacta es: $\binom{r}{2} + \binom{s}{2} > rs \iff (r-s)^2 > r+s$, que solo ocurre cuando $|r-s| \ge 2$ (si $r+s = n$ es fijo), y específicamente $\max(r,s) \ge \lceil (n+2)/2 \rceil > n/2$, lo que confirma la condición. Este problema ilustra cómo la estructura bicolor de una relación entre enteros (paridad de la suma) lleva a un conteo de tipo Ramsey.

La conexión con Ramsey: podemos ver las paridades como una 2-coloración de los vértices (no aristas) de $K_n$: cada $a_i$ es "rojo" (par) o "azul" (impar). Las celdas rojas son aristas entre vértices del mismo color, las azules entre colores distintos. La pregunta es: ¿cuándo hay más aristas monocromáticas que bicromaticas? La respuesta depende de la distribución de colores. Cuando ambos colores tienen exactamente $n/2$ vértices, hay el máximo de aristas bicromaticas ($n^2/4$) y el mínimo de monocromáticas —este es el extremo del grafo bipartito completo balanceado $K_{n/2, n/2}$, que es precisamente el grafo de Turán $T(n,2)$ que veremos en el Capítulo 2.

Construcciones extremales: geometría finita como herramienta

Para la cota inferior $R(k,k) > n$ (es decir, para construir una 2-coloración de $K_n$ sin $K_k$ monocromático), los grafos de Paley y las cuadrículas sobre cuerpos finitos son las herramientas más poderosas. El grafo de Paley $P(q)$ (para primo $q \equiv 1 \pmod{4}$) tiene como vértices los elementos de $\mathbb{F}_q$ (el cuerpo con $q$ elementos) y conecta $x$ con $y$ si $x - y$ es un residuo cuadrático no nulo en $\mathbb{F}_q$.

El grafo de Paley $P(q)$ es un grafo autorreemplazante ("self-complementary"): $P(q) \cong \overline{P(q)}$ (el grafo es isomorfo a su complemento). Esto significa que la coloración donde las aristas de $P(q)$ son rojas y las de $\overline{P(q)}$ son azules es una 2-coloración "simétrica". El número de clique $\omega(P(q))$ está acotado superiormente por $O(\sqrt{q} \log q)$, lo que da la cota inferior $R(k,k) > q$ para $k \approx \sqrt{q} \log q$. Traducido: $R(k,k) > q$ para $q \sim k^2 / \log^2 k$, dando $R(k,k) > k^2 / \log^2 k$. Esta es una cota más débil que la de Erdős ($R(k,k) > 2^{k/2}$), pero tiene la ventaja de ser una construcción explícita y determinística.

Para el IMO y el Shortlist, los grafos de Paley aparecen implícitamente en varios problemas de coloración. El estudiante que conoce la construcción puede verificar rápidamente si un ejemplo que busca puede ser de tipo "diferencias cuadráticas módulo primo", que es la esencia de Paley.

El plano proyectivo de orden $q$ (para potencias de primo $q$) proporciona la construcción para $R(3,3,3) > 16$ mencionada antes. Los $q^2 + q + 1$ puntos del plano proyectivo $PG(2,q)$ para $q = 4$ dan $21$ puntos, pero la construcción de $K_{16}$ sin triángulo monocromático en tres colores usa solo la estructura de incidencia de las $21$ rectas de $PG(2,4)$ (el plano proyectivo de orden $4$). Los tres colores corresponden a tres familias de líneas paralelas en el plano afín $AG(2,4)$ (el plano proyectivo sin la recta del infinito), y la verificación de que no hay triángulo monocromático se reduce a comprobar que ninguna terna de puntos está en la misma familia de líneas.

Para las competencias, lo importante no es conocer todos los detalles de la geometría proyectiva, sino tener la intuición de que las construcciones extremales para Ramsey "vienen de la geometría finita" y que los primos y las potencias de primo tienen un papel especial. Cuando en un problema de construcción el número de vértices es de la forma $q^2 + q$ o $q^2 - 1$ para primo $q$, esto es una fuerte señal de que la construcción óptima es de tipo Paley o proyectivo.

Galería de problemas: del IMO al Shortlist

Para consolidar la metodología, analizamos brevemente tres problemas adicionales del olimpismo internacional que utilizan ideas de Ramsey, señalando en cada caso el "disfraz" y la técnica de solución.

IMO 1964 Problema 4 (reformulado): "Encuentra el menor $n$ tal que en toda permutación de $\{1, \ldots, n\}$ existe una subsecuencia monótona de longitud 5." Por el Teorema de Erdős–Szekeres, la respuesta es $n = 17$ (en toda permutación de $4 \cdot 4 + 1 = 17$ elementos hay una subsecuencia creciente o decreciente de longitud 5). El teorema dice: toda permutación de más de $(r-1)(s-1)$ elementos tiene una subsecuencia creciente de longitud $r$ o una decreciente de longitud $s$. Este es Ramsey disfrazado en permutaciones: la 2-coloración es la relación de orden entre pares $(i,j)$, y el clique monocromático es la subsecuencia monótona.

IMO Shortlist 2006 C3: "Sean $n$ personas sentadas en círculo. Colorea cada arco entre personas adyacentes de rojo o azul, y cada cuerda entre personas no adyacentes de verde. Demuestra que existen tres personas que determinan tres aristas del mismo color si $n$ es suficientemente grande." Este es Ramsey en $K_n$ con tres colores pero con estructura circular impuesta. La solución combina el argumento de paloma con el hecho de que el número cromático del grafo de incomparabilidad circular está acotado.

Olimpiada de Rusia 2019, Problema 7: "En una competencia de $n$ participantes, cada par de participantes es "compatibles" o "incompatibles". Se sabe que si $A$ y $B$ son compatibles y $B$ y $C$ son compatibles, entonces $A$ y $C$ son incompatibles. Demuestra que $n \le 4$." La condición dice que la relación de compatibilidad no contiene triángulos — el grafo de compatibilidad es $K_3$-free. Y además la incompatibilidad también es $K_3$-free (por la misma condición aplicada con los roles intercambiados). Combinando: $G$ y $\overline{G}$ son ambos $K_3$-free, lo que implica que $R(3,3) = 6 > n$, así $n \le 5$. Con el argumento más cuidadoso, $n \le 4$.

La diversidad de estos ejemplos ilustra el punto central de esta lección: los problemas de tipo Ramsey son omnipresentes en olimpiadas, desde el IMO hasta los clasificatorios nacionales. La habilidad de reconocer el modelo correcto (grafo, coloración, estructura objetivo) y aplicar el argumento adecuado (paloma, conteo, construcción explícita) es la que separa las soluciones de 7 puntos de las de 0 puntos. Esta habilidad se desarrolla con práctica deliberada: resolviendo problemas variados, analizando las soluciones cuando uno se bloquea, y reflexionando sobre qué elemento del problema activó o debería haber activado el patrón de Ramsey.