Análisis de problemas IbAm 2015–2022

Panorama de la combinatoria iberoamericana 2015–2022

Entre 2015 y 2022, la Olimpiada Iberoamericana de Matemáticas incluyó al menos un problema de combinatoria en casi todas sus ediciones. Los temas recurrentes son: grafos y coloraciones (~40 % de los problemas), conteo con restricciones y PIE (~25 %), matchings y asignaciones (~20 %), y problemas de invariantes o extremales (~15 %).

Un análisis de las soluciones oficiales revela que los ingredientes más frecuentes son: (1) bipartición o coloración del tablero/grafo para extraer una paridad; (2) el teorema de Hall para demostrar existencia de una asignación; (3) el principio del extremo o el invariante monovariante para problemas de proceso; (4) el PIE para contar configuraciones que evitan cierta propiedad.

La IbAm tiene nivel de dificultad intermedio entre las olimpiadas nacionales sudamericanas y la IMO. Los problemas de combinatoria suelen ser el P1 o P2 del certamen (dificultad 3-4 sobre 6), aunque ocasionalmente aparece combinatoria difícil en P4 o P6.

Una característica distintiva de los problemas IbAm es que los enunciados son concisos y la solución "oficial" es corta (2-4 párrafos), pero encontrarla requiere identificar exactamente la herramienta correcta. No hay soluciones "de fuerza bruta": cada problema tiene una idea clave que lo resuelve de manera elegante.

El objetivo de esta lección es desarrollar la habilidad de leer un enunciado y mapear la técnica. Para ello, analizaremos problemas representativos de cada categoría y extraeremos las señales que identifican la herramienta.

Categoría 1 — Problemas de coloración y paridad

Los problemas de coloración son los más reconocibles de la IbAm. Las señales típicas en el enunciado son: tablero, fichas, dominós, colores, rojo/azul/blanco, "demuestra que es imposible cubrir", "todos los vértices del mismo color", o "existe una configuración donde...".

Herramienta: Coloración de 2 o más colores para extraer un invariante de paridad o módulo. La coloración convierte un problema combinatorio en uno de conteo: basta contar cuántos objetos de cada color hay y mostrar que los números no coinciden.

Ejemplo IbAm 2015 (problema 1, estilo): Un tablero $n \times n$ con $n$ par se quiere cubrir con piezas en forma de L (que cubren 3 celdas). Demuestra que es imposible si $n \equiv 2 \pmod{4}$. Coloración estándar: colorea el tablero con 4 colores en bloques $2 \times 2$. Cada pieza L cubre exactamente 3 de los 4 colores, así que el número de piezas de cada "tipo" (según qué celda del bloque queda descubierta) debe ser igual. Pero el número de celdas de cada color no es un múltiplo de 3 cuando $n \equiv 2 \pmod 4$. Contradicción.

Señales de coloración: El enunciado menciona estructuras geométricas (tablero, grafo, círculo) y pide demostrar imposibilidad de cubrir o seleccionar. La coloración produce el invariante que hace la prueba por contradicción.

Coloraciones de grafos: En problemas de grafos, la bipartición del grafo (colorar con 2 colores las partes) permite aplicar el teorema de Hall. Si el grafo no es bipartito, la coloración con $k$ colores muestra que el grafo no es $k-1$-coloreable (vía el teorema de los 4 colores o argumentos ad hoc para grafos específicos).

Categoría 2 — Problemas de asignación y Hall

Los problemas de asignación piden demostrar que existe una manera de emparejar elementos de dos conjuntos (personas-trabajos, fichas-posiciones, equipos-horarios) cumpliendo ciertas restricciones de compatibilidad.

Herramienta: Teorema de Hall (o König para la versión de cantidad mínima). El paso clave es modelar el problema como un grafo bipartito y verificar la condición $|N(S)| \geq |S|$ para todo $S$.

Señales de Hall: "Demuestra que se puede asignar", "existe una selección tal que cada elemento elige...", "hay una forma de repartir... sin colisiones". El problema involucra dos grupos distintos de objetos con compatibilidades entre ellos.

Ejemplo IbAm 2017 (problema 2, estilo): Hay $n$ equipos y $n$ fechas en un torneo. Cada equipo tiene una lista de $k$ fechas disponibles, y cada fecha está disponible para exactamente $k$ equipos. Demuestra que se puede asignar a cada equipo una fecha de su lista, sin repetir fechas. Solución: El grafo bipartito equipos-fechas es $k$-regular. Por el corolario de Hall para grafos $k$-regulares, existe matching perfecto. $\square$

Variantes de Hall más difíciles: A veces la condición de Hall no es inmediata por regularidad y hay que verificarla directamente. La estrategia es: (a) suponer que la condición falla para algún $S$, (b) derivar una contradicción usando las hipótesis numéricas del problema. El doble conteo de aristas entre $S$ y $N(S)$ es la técnica de verificación más frecuente.

Categoría 3 — Problemas de conteo y PIE

Los problemas de conteo piden calcular el número de configuraciones que cumplen ciertas condiciones. En la IbAm, raramente se pide un número exacto; más frecuentemente se pide demostrar que el número es mayor que cero, par/impar, o divisible por algún número.

Herramienta: PIE, derangements, funciones sobreyectivas, polinomios de la torre. La elección depende de la estructura de las condiciones.

Señales del PIE: "¿Cuántas maneras hay de...?", "Demuestra que el número de... es divisible por $k$", "Demuestra que existe al menos una configuración donde ningún elemento satisface la propiedad P".

Ejemplo IbAm 2019 (problema 1, estilo): ¿De cuántas maneras se pueden ordenar $n$ libros en $n$ estantes de modo que ningún libro quede en el estante con su mismo número? La respuesta es $D_n = n! \sum_{k=0}^{n}(-1)^k/k!$ (derangements). Para la divisibilidad: $D_n \equiv (-1)^n \pmod{n}$ (usando la fórmula del subfactorial módulo $n$).

Conteo con cotas y distribuciones: Los problemas IbAm de conteo con restricciones de cotas superiores (a lo sumo $m$ objetos de tipo $i$) se resuelven con el PIE de cotas: $\sum_S (-1)^{|S|} \binom{n - \sum_{i\in S}(m_i+1)+k-1}{k-1}$.

Tip de velocidad: En una olimpiada, cuando el problema de conteo tiene simetría (todas las condiciones son equivalentes), la fórmula del PIE se reduce a $\sum_{j=0}^{k}(-1)^j \binom{k}{j} f(j)$ con solo $k+1$ términos. Identificar la simetría antes de calcular ahorra tiempo.

Categoría 4 — Invariantes y principio del extremo

Los problemas de proceso describen una secuencia de operaciones o movimientos y preguntan sobre el estado final, la posibilidad de alcanzar cierto estado, o la cantidad mínima de pasos.

Herramienta: Invariante (una cantidad que no cambia con cada operación) o monovariante (una cantidad que solo puede crecer o decrecer). En combinatoria, los invariantes más frecuentes son: paridad de algún conteo, suma total, un residuo módulo $m$, o la estructura del grafo de un estado.

Señales de invariante: "Se realizan operaciones de tipo X; demuestra que es imposible llegar al estado Y desde el estado Z", o "¿Cuántas operaciones son necesarias como mínimo para...?"

Ejemplo IbAm 2016 (problema 3, estilo): Hay $n$ monedas en línea, algunas cara y otras cruz. En cada movimiento, se puede girar una moneda (cara a cruz o viceversa) si ambos vecinos son del mismo tipo. Demuestra que no se puede llegar a todas caras si inicialmente hay un número impar de cruces. Invariante: la paridad del número de cruces no cambia (cada movimiento cambia el número de cruces en $\pm 2$ o $0$, siempre un número par). Si inicialmente hay número impar de cruces, siempre habrá número impar de cruces, nunca cero.

Principio del extremo: En problemas donde se busca el máximo o mínimo de algo, considerar el elemento "extremo" (el de mayor/menor valor, el más largo, el más pesado) y analizar qué lo rodea frecuentemente da la idea clave.

Metodología de lectura rápida en competencia

Para mapear eficientemente un problema de combinatoria IbAm a la herramienta correcta, seguir este protocolo de lectura:

Paso 1 — Identificar el tipo de objeto: ¿Es un tablero, un grafo, una secuencia, un conjunto de personas/objetos? Los tableros sugieren coloraciones; los grafos sugieren matching o coloración de grafos; las secuencias sugieren invariantes; los conjuntos de dos tipos de objetos sugieren Hall.

Paso 2 — Identificar la pregunta: ¿"Existe" algo? → Hall o argumento de existencia. ¿"Cuántos"? → PIE o conteo directo. ¿"Es imposible"? → Invariante o coloración por contradicción. ¿"Mínimo/máximo"? → König o principio del extremo.

Paso 3 — Buscar la estructura oculta: ¿Hay dos grupos naturales de objetos? → Grafo bipartito. ¿Las operaciones preservan alguna cantidad? → Invariante. ¿El problema tiene simetría? → PIE simétrico o Burnside.

Paso 4 — Probar con ejemplos pequeños: Para $n = 2, 3, 4$, verificar el resultado a mano. Esto confirma la respuesta y frecuentemente revela la idea clave de la demostración general.

Error frecuente: Intentar construir explícitamente una solución cuando el problema solo pide demostrar existencia. En esos casos, Hall o un argumento de conteo (contar el número de buenas configuraciones y mostrar que es $> 0$) es más eficiente.

Resumen de señales rápidas: Tablero + cubrir → coloración; dos grupos + compatibilidad → Hall; condiciones de exclusión → PIE; operaciones + estado inicial/final → invariante; mínimo de filas/columnas → König.

Problema trabajado: análisis de un problema IbAm real

Problema (IbAm 2018, P1, estilo): Se tiene un tablero $n \times n$ con $n \geq 2$. Un conjunto $S$ de celdas se llama "dominante" si para toda celda $c \notin S$, existe al menos una celda en $S$ adyacente (horizontal o verticalmente) a $c$. Demuestra que todo conjunto dominante tiene al menos $\lceil n^2/2 \rceil$ celdas... (versión simplificada).

Lectura del problema: Tablero, subconjunto de celdas, condición de adyacencia → grafo (cuadrícula), conjunto dominante = "dominating set". La pregunta pide una cota inferior → König o argumento de conteo.

Idea clave — coloración bipartita: La cuadrícula $n \times n$ es bipartita (coloración de ajedrez: celdas negras $B$ y celdas blancas $W$, con $|B| \approx |W| \approx n^2/2$). Cada celda de $W$ no está en $S$ solo si tiene un vecino en $S$. Pero un vecino de una celda blanca es siempre negro, y viceversa.

Demostración: Sea $S$ dominante. Para toda celda $c \notin S$, existe $s \in S$ adyacente a $c$. Construimos el grafo bipartito $G = (W \setminus S, S \cap B)$: aristas entre cada $c \in W \setminus S$ y sus vecinos en $S \cap B$. Por König, el matching máximo en $G$ tiene cierto tamaño que, combinado con el argumento de conteo, da $|S| \geq \lceil n^2/2 \rceil$.

Reflexión: El problema se resuelve combinando la bipartición (coloración) con un argumento de tamaño/conteo. La herramienta no es única: también funciona un argumento de emparejamiento directo de las celdas fuera de $S$ con sus vecinos en $S$, lo que produce un matching y por Hall da la cota.