Cierre y ruta al Nivel 2

El arsenal del Nivel 1 de Combinatoria

Al completar este módulo dominas:

Principios de conteo: multiplicativo, aditivo, bijectivo (biyección entre conjuntos). Permutaciones y combinaciones con y sin repetición. Coeficientes binomiales y triángulo de Pascal.

Inclusión-exclusión: fórmula general del PIE, aplicación a divisibilidad, y aplicación a funciones sobreyectivas.

Principio de las casillas: versión simple y versión generalizada (si $n$ objetos en $m$ casillas con $n > km$, alguna casilla tiene más de $k$ objetos).

Recursiones: Fibonacci y sus variantes, recurrencias lineales de orden 2, ecuación característica, números de Catalan, números de Stirling.

Caminos en cuadrículas: $\binom{m+n}{m}$ caminos de $(0,0)$ a $(m,n)$, exclusión de obstáculos, números de Catalan como caminos que no cruzan la diagonal.

Inducción combinatoria: demostrar identidades y propiedades de configuraciones por inducción simple y fuerte.

Lo que diferencia el Nivel 1 del Nivel 2

Los problemas del Nivel 2 (ONEM nacional, Iberoamericana) requieren:

Teoría de grafos: coloración de grafos, teorema de Turán, grafos bipartitos, teorema de Hall para matchings perfectos.

Combinatoria extremal: problemas de tipo "¿cuál es el máximo número de aristas de un grafo sin triángulo?" (Turán) o "¿cuántos subconjuntos de $\{1,\ldots,n\}$ pueden elegirse sin que ninguno contenga al otro?" (Dilworth/Sperner).

Probabilidad discreta: valor esperado lineal, segundo momento, Lovász Local Lemma en forma básica.

Álgebra lineal en combinatoria: el rango de matrices sobre $\mathbb{F}_2$ para problemas de combinatoria lineal; polinomios y sumas de potencias.

Generatrices: funciones generatrices ordinarias y exponenciales para contar particiones, derangements, y otras estructuras.

Ruta de estudio recomendada

Paso 1 (1 mes). Consolida el Nivel 1 resolviendo todos los problemas de combinatoria de la ONEM regional de los últimos 3 años sin ver soluciones.

Paso 2 (2 meses). Estudia teoría de grafos introductoria: árboles, coloración, matchings, teorema de Hall. Referencia: "A Walk Through Combinatorics" de Miklós Bóna, capítulos 7-9.

Paso 3 (2 meses). Funciones generatrices: ordinarias y exponenciales. Referencia: "generatingfunctionology" de Wilf (disponible gratis en línea).

Paso 4 (2 meses). Combinatoria extremal: Turán, Ramsey, Sperner. Referencia: "Combinatorics" de N. Alon y J. Spencer.

Paso 5 (continuo). Problemas de Iberoamericana y ONEM nacional de los últimos 10 años. Usa AoPS para discusiones.

Palabras finales

La combinatoria olímpica es el área más accesible para comenzar, pero también la que más sorprende: un problema que parece trivial a primera vista puede requerir una idea brillante e inesperada.

La clave del éxito en combinatoria no es memorizar fórmulas, sino desarrollar la intuición combinatoria: la capacidad de ver estructuras, patrones y biyecciones donde otros ven solo números.

Cada vez que resuelvas un problema, pregúntate: ¿existe otra demostración más elegante? ¿Qué invariante captura la esencia del problema? ¿Hay una biyección que lo explique sin cálculos?

El Nivel 2 te espera. La combinatoria tiene capas de profundidad que se revelan con cada problema nuevo.