Cierre del módulo + ruta hacia Nivel 3

Lo que aprendiste en los 8 capítulos de este módulo

Al completar Combinatoria Nivel 2 dominas un arsenal que cubre la gran mayoría de los problemas P1–P3 de la Iberoamericana y el Cono Sur. Aquí el mapa completo:

Capítulos 1–2 (Fundamentos avanzados): Principio de inclusión-exclusión con cotas, polinomio de la torre, números de Stirling, particiones de conjuntos. La idea central: contar por complemento y por descomposición en clases.

Capítulos 3–4 (Teoría de grafos): Grafos bipartitos, teorema de Hall (matching perfecto), teorema de König (cobertura mínima = matching máximo), coloración de grafos y polinomio cromático. La idea central: modelar el problema como un grafo y usar la dualidad Hall-König.

Capítulo 5 (Combinatoria extremal básica): Principio del extremo, teorema de Turán, sistemas de conjuntos sin inclusión (Sperner), cadenas y antichains. La idea central: maximizar o minimizar una cantidad combinatoria y encontrar la configuración óptima.

Capítulo 6 (Concursos iberoamericanos): Lectura estratégica de problemas IbAm, combinación de Hall + König + PIE + coloraciones, redacción de demostraciones completas. La idea central: identificar rápidamente la herramienta en el enunciado.

Capítulos 7–8 (Probabilidad discreta e invariantes): Método del primer momento (valor esperado), principio del segundo momento, invariantes y monovariantes en procesos. La idea central: existencia por argumento probabilístico, imposibilidad por invariante.

El arsenal del Nivel 2 en una tabla

Señal en el enunciado → Herramienta → Primer movimiento:

Dos grupos + compatibilidades + "¿existe asignación?" → Teorema de Hall → construir grafo bipartito y verificar $|N(S)| \geq |S|$ por doble conteo.

Mínimo de líneas que cubren celdas marcadas → Teorema de König → grafo bipartito, $\nu(G) = \tau(G)$.

Condiciones de exclusión + "¿cuántas configuraciones?" → PIE → definir conjuntos "malos", calcular $|\bigcap_{i \in S} A_i|$.

Tablero + cubrimiento imposible → Coloración de ajedrez → contar celdas de cada color.

Operaciones en grafo/tablero + "¿es posible llegar a?" → Invariante/monovariante → identificar cantidad conservada o monótona.

Máximo de aristas sin triángulos → Turán → $ex(n, K_3) = \lfloor n^2/4 \rfloor$, igualdad en $K_{n/2,n/2}$.

"Existe una configuración con propiedad P" → Método probabilístico → construir distribución aleatoria y calcular $\mathbb{E}[\#\text{elementos con P}] > 0$.

Qué hace más difícil el Nivel 3: Ramsey, probabilístico y extremal

El salto de Nivel 2 a Nivel 3 (problemas P4–P6 de la IbAm, o P1–P3 de la IMO) no es un salto de herramientas, sino de profundidad en su uso. Las tres grandes áreas que marcan el Nivel 3:

Teoría de Ramsey. El teorema de Ramsey dice que para todo $r, s \geq 1$, existe $R(r,s)$ tal que cualquier 2-coloración de las aristas de $K_{R(r,s)}$ contiene un $K_r$ monocromático rojo o un $K_s$ monocromático azul. En el Nivel 3, los problemas piden: (a) acotar $R(r,s)$ por arriba y por abajo; (b) aplicar Ramsey para demostrar la existencia de estructuras monocromáticas en configuraciones más generales; (c) usar Ramsey hipergráfico ($k$-coloraciones de $k$-tuplas). La cota superior estándar $R(r,s) \leq \binom{r+s-2}{r-1}$ se demuestra por inducción; la cota inferior (construcciones explícitas) es más difícil.

Método probabilístico. Más allá del primer momento, el Nivel 3 usa: el Lema Local de Lovász (LLL) para demostrar existencia de coloraciones que evitan "malos" eventos raros; el método de segundo momento para dar cotas superiores al número de cliques en grafos aleatorios; y la eliminación probabilística (deletar un elemento de un conjunto aleatorio para mejorar la estructura). El LLL es el resultado más poderoso: si cada evento "malo" $A_i$ tiene probabilidad $\leq p$ y depende de a lo sumo $d$ otros eventos, y $ep(d+1) \leq 1$, entonces todos los eventos malos pueden evitarse simultáneamente.

Grafos extremales avanzados. El teorema de Kruskal-Katona (el subconjunto de $k$-tuplas que minimiza el número de $(k-1)$-tuplas es el "segmento inicial" del orden colex). El teorema de Szemerédi sobre progresiones aritméticas en conjuntos densos. La conjetura de Turán para hipergrafos (aún abierta en general). Estos resultados requieren combinatoria algebraica y herramientas del análisis.

Hoja de ruta para estudiar Nivel 3

Aquí la progresión recomendada para pasar de este módulo a la competencia IMO:

Mes 1-2 — Consolidación: Resuelve todos los problemas de combinatoria de la IbAm 2010–2022 sin ver soluciones. Para cada problema, escribe la solución completa y luego compara con la solución oficial. Identifica los patrones que no dominas.

Mes 3-4 — Ramsey y coloraciones: Estudia el capítulo de Ramsey en "Probabilistic Method" de Alon-Spencer (capítulo 1, sección sobre Ramsey). Resuelve los primeros 20 problemas del conjunto de Ramsey en AoPS. Aprende las cotas $R(r,s) \leq \binom{r+s-2}{r-1}$ y $R(k,k) > 2^{k/2}$ (construcción de Erdős).

Mes 5-6 — Método probabilístico: Lee "The Probabilistic Method" de Alon y Spencer, capítulos 1-5. Enfócate en el primer momento, el segundo momento y el Lema Local de Lovász. Resuelve los ejercicios marcados con (**) en cada capítulo.

Mes 7-8 — Grafos extremales: Estudia el teorema de Szemerédi de regularidad (lema de regularidad), sus aplicaciones a la cota del teorema de Ramsey, y la demostración del teorema de Roth sobre progresiones aritméticas de longitud 3. Referencia: "Graph Theory" de Diestel, capítulo 7.

Continuo — Problemas IMO: Resuelve todos los problemas de combinatoria de la IMO 2005–2024. Usa los recursos de AoPS y el "IMO Compendium". Los problemas C6–C9 (los más difíciles del shortlist) son el objetivo final.

Cierre: la belleza de la combinatoria olímpica

La combinatoria olímpica tiene una cualidad que la distingue de otras áreas: sus problemas más bellos se resuelven con una sola idea, clara y elegante, que hace que la solución parezca obvia en retrospectiva. Ese momento de claridad — cuando ves la biyección correcta, el invariante oculto, o el grafo que modela el problema — es lo que hace que valga la pena cada hora de estudio.

A lo largo de este módulo, has aprendido a ver estructuras donde otros ven caos: dos grupos de objetos con compatibilidades se convierten en un grafo bipartito y el teorema de Hall; una sucesión de operaciones se convierte en un invariante; un tablero complicado se ilumina con una coloración de dos colores.

El Nivel 3 añade nuevas herramientas — Ramsey, probabilístico, extremal — pero la filosofía es la misma: buscar la estructura oculta, modelarla con el lenguaje correcto, y dejar que la maquinaria matemática haga el trabajo.

Un consejo final: los mejores competidores de combinatoria no memorizan soluciones, sino que memorizan ideas. Cada vez que resuelvas un problema, pregúntate: ¿cuál fue la idea clave? ¿Podría la misma idea resolver otros problemas? ¿Hay una forma más elegante de expresar esta demostración? Esa reflexión es lo que construye la intuición combinatoria que distingue a un competidor bueno de uno excepcional.

¡Hasta el Nivel 3, y que los derangements te sean favorables!