Módulos / combinatoria-3 / Capítulo 6 — Problemas IMO de combinatoria: taxonomía / Lección 6.4

Cómo escribir una solución completa de combinatoria IMO

Lección 6.4·Capítulo 6 — Problemas IMO de combinatoria: taxonomía·15 min·Piloto

▶

Video en producción

El contenido pedagógico de esta lección ya está completo y lo puedes leer abajo. El video con la voz de Eduardo Espinoza Ramos se produce según la Política de IA.

Disclosure de IA: al publicarse, este contenido reproducirá digitalmente, con autorización expresa del autor, la voz y fisonomía de Eduardo Espinoza Ramos. Curaduría revisada por matemáticos profesionales. Política completa →

Objetivo de la lección

Dominar la redacción de soluciones de combinatoria de nivel IMO: la estructura estándar de una solución (enunciado del resultado, lemas auxiliares, construcción o demostración principal, verificación del caso límite), el nivel adecuado de detalle en los argumentos de conteo y construcción, la presentación de argumentos probabilísticos no constructivos, y los errores más comunes que cuestan puntos en el jurado IMO. Aprender a revisar la propia solución con la mirada de un jurado.

La estructura de una solución IMO de combinatoria

Una solución completa de combinatoria IMO tiene cuatro secciones:

(1) Enunciado del resultado. En una o dos oraciones, se enuncia qué se va a demostrar. Si el problema pide "hallar todos $n$ tales que...", se enuncia explícitamente el conjunto de $n$ (por ejemplo, "La respuesta es: $n$ si y solo si $n \equiv 1 \pmod{3}$ "). Si el problema pide demostrar una afirmación, se la reitera brevemente.

(2) Lemas auxiliares. Si la demostración requiere resultados intermedios no triviales, se los enuncia como lemas con sus pruebas. Cada lema debe tener: enunciado claro, demostración autocontenida, y uso explícito en la demostración principal.

(3) Demostración principal. La cadena de argumentos que conduce de las hipótesis a la conclusión. En combinatoria, esto incluye: la construcción (si se pide existencia), el invariante o semivariante (si se pide no-alcanzabilidad), o la estrategia ganadora (si es un juego).

(4) Verificación / caso límite. Para problemas de optimización (máximo, mínimo), se verifica que el extremo se alcanza (construyendo el ejemplo óptimo). Para problemas de existencia, se verifica que la construcción satisface todas las condiciones. Para problemas de no-existencia, se verifica que el invariante es realmente un invariante (aplicando la definición a cada tipo de paso).

El nivel de detalle correcto: qué explicar y qué omitir

Los jurados IMO puntúan la corrección matemática, no la longitud. Las siguientes reglas calibran el nivel de detalle:

Siempre explicar: (a) Por qué una cantidad es un invariante (verificar cada tipo de operación, no solo decir "claramente es invariante"). (b) Por qué la construcción satisface todas las condiciones del enunciado (no solo la condición principal). (c) La base de la inducción y el paso inductivo, incluyendo la hipótesis inductive explícita. (d) Por qué el argumento de extremo (o de mínimo) funciona: la existencia del extremo debe ser justificada (conjuntos finitos, función de costo acotada).

Puede omitirse (asumirse conocido): (a) Fórmulas combinatorias estándar ( $\binom{n}{k}$ , identidades de sumas). (b) El Teorema de Hall sin prueba, si su aplicación es estándar. (c) Pasos algebraicos elementales (simplificaciones de polinomios, factorizaciones estándar). (d) El Principio de Pigeonhole elemental para divisiones simples.

Nunca omitir: La verificación de que el caso extremo (igualdad en la cota) es alcanzable, en problemas de optimización. Omitir la construcción del ejemplo extremal cuesta entre 1 y 2 puntos en el jurado.

Regla de oro: después de escribir la solución, leerla asumiendo que el lector es un matemático que no ha visto el problema antes. ¿Cada paso es justificado? ¿No hay saltos lógicos? ¿El argumento funciona también para los casos degenerados ( $n = 1$ , conjunto vacío, etc.)?

Presentar un argumento de conteo doble

El conteo doble es la técnica más frecuente en la prueba IMO de combinatoria. Su presentación debe seguir el esquema:

Paso 1: Definir el conjunto que se va a contar. ("Consideremos el conjunto $\mathcal{P}$ de todos los pares $(x, S)$ tales que $x \in S$ y $S$ satisface la propiedad $P$ .")

Paso 2: Contar por una perspectiva. ("Por un lado, fijando $x$ , el número de conjuntos $S$ que contienen a $x$ y satisfacen $P$ es $f(x)$ , luego $|\mathcal{P}| = \sum_x f(x)$ .")

Paso 3: Contar por la otra perspectiva. ("Por otro lado, fijando $S$ , cada $S$ con $P$ contribuye $|S|$ pares, luego $|\mathcal{P}| = \sum_{S: P(S)} |S|$ .")

Paso 4: Igualar y concluir. ("Igualando: $\sum_x f(x) = \sum_{S: P(S)} |S|$ . Esto implica...")

El error más común: no distinguir claramente qué se fija y qué varía en cada perspectiva. Si el conjunto que se cuenta no está bien definido, el argumento se derrumba. La definición del conjunto en Paso 1 debe ser lo más explícita posible.

Desigualdades de conteo. En lugar de igualdades exactas, a menudo se cuenta para obtener una cota: $|\mathcal{P}| \le X$ (por una perspectiva) y $|\mathcal{P}| \ge Y$ (por la otra), concluyendo $Y \le X$ . La presentación es idéntica pero se indica la dirección de la desigualdad en cada paso.

Presentar un argumento probabilístico no constructivo

Los argumentos del método probabilístico (Capítulo 2) son frecuentes en problemas C5–C8 del Shortlist. Su presentación en una solución IMO debe seguir:

Paso 1 — Espacio de probabilidad. ("Consideramos una coloración aleatoria de los vértices con colores $1, \ldots, k$ , donde cada vértice recibe cada color independientemente con probabilidad $1/k$ .")

Paso 2 — Evento y su probabilidad. ("Sea $X$ el número de aristas monocrómaticas. Calculamos $\mathbb{E}[X] = m/k$ (donde $m$ es el número total de aristas), pues cada arista es monocrómatica con probabilidad $1/k$ .")

Paso 3 — Conclusión de existencia. ("Si $\mathbb{E}[X] < c$ , entonces existe una coloración con $X < c$ , es decir, con menos de $c$ aristas monocrómaticas. En particular, eliminando un vértice de cada arista monocrómatica se obtiene un subconjunto de al menos $n - c$ vértices con la propiedad deseada.")

Cuidado: el paso de $\mathbb{E}[X] < c$ a "existe coloración con $X < c$ " debe ser explícito. La justificación: si $\mathbb{E}[X] < c$ (o $\le c - 1$ para entero), entonces el evento $\{X < c\}$ tiene probabilidad positiva, luego existe una coloración con $X < c$ . Nunca saltar este paso.

El Lovász Local Lemma. Si la solución usa el LLL, la presentación debe: definir los eventos "malos", verificar la condición de dependencia ( $d$ -dependencia o condición simétrica $ep(d+1) \le 1$ ), y concluir que la probabilidad de que no ocurra ningún evento malo es positiva. Cada uno de los tres pasos debe ser explícito.

ep(d+1) \le 1 \implies \mathbb{P}\!\left(\bigcap_i \overline{A_i}\right) > 0

Los 7 errores más frecuentes en soluciones IMO de combinatoria

Error 1: no construir el ejemplo extremal. En problemas "halla el mínimo/máximo de $f(n)$ ", demostrar $f(n) \ge c$ (o $\le c$ ) sin exhibir un ejemplo donde $f(n) = c$ da como máximo 5 puntos (de 7). La construcción es obligatoria.

Error 2: invariante no verificado. Decir "la cantidad $Q$ es invariante" sin verificar cada tipo de operación. El jurado requerirá verificar caso a caso (si hay $k$ tipos de operación, verificar los $k$ casos).

Error 3: inducción sin hipótesis explícita. Escribir "por inducción" sin enunciar la hipótesis inductiva. La hipótesis inductiva debe ser lo suficientemente fuerte para que el paso funcione (a menudo es más fuerte que lo que se quiere demostrar).

Error 4: salto cuantitativo en el método probabilístico. De " $\mathbb{E}[X] < n$ " concluir "existe una coloración con $X < n$ " es válido, pero concluir "existe una coloración con $X = 0$ " requiere $\mathbb{E}[X] < 1$ , no solo $< n$ .

Error 5: ignorar el caso de igualdad. En desigualdades de conteo ( $\sum \ge k \cdot m$ ), el caso de igualdad suele dar información adicional sobre la estructura del objeto extremal. Ignorarlo puede hacer que la solución sea correcta para la cota pero incompleta para la caracterización.

Error 6: construcción no verificada. En problemas de existencia, construir un objeto sin verificar que satisface todas las condiciones. Cada condición del enunciado debe verificarse para la construcción.

Error 7: usar un teorema conocido sin enunciarlo. Si la solución usa Hall, Turán, Ramsey o Szemerédi, enunciar el teorema (al menos brevemente) antes de aplicarlo, e indicar cómo se aplica (con qué parámetros). "Por Hall, el emparejamiento existe" sin verificar la condición de Hall no recibe crédito.

Problemas del Capítulo 6 — con solución

8 problemas verificados. Intenta cada uno antes de abrir la solución.

C3-6.1★★★★IMO Shortlist 2007 C3

Sea $n$ un entero positivo. Una partición de $\{1, 2, \ldots, n\}$ en conjuntos $A$ y $B$ se llama buena si $\sum_{a \in A} a^2 = \sum_{b \in B} b^2$ . Determina todos los $n$ para los cuales existe una partición buena de $\{1, 2, \ldots, n\}$ .

C3-6.2★★★★IMO Shortlist 2013 C2

Sea $n \ge 3$ un entero. Se tienen $n$ puntos en posición general en el plano (no hay tres colineales). Se colorea cada punto de rojo o azul. Una triangulación de los puntos se dice bicolor si los tres vértices de todo triángulo son de ambos colores (no todo el mismo color). Demuestra que para toda coloración con al menos un punto rojo y al menos un punto azul, existe una triangulación bicolor.

C3-6.3★★★★IMO 2014 Problema 6

Sea $a_1 < a_2 < \cdots < a_n$ una secuencia de enteros. Un subconjunto $S = \{a_{i_1}, a_{i_2}, \ldots, a_{i_k}\}$ (con $i_1 < i_2 < \cdots < i_k$ ) se llama bueno si los valores $a_{i_j+1} - a_{i_j}$ son todos iguales para $j = 1, \ldots, k-1$ (es decir, $S$ es una progresión aritmética que toma valores en la secuencia). ¿Es verdad que para toda secuencia $a_1 < \cdots < a_n$ de $n$ enteros con $a_i \in \{1, 2, \ldots, 2n\}$ , existe un subconjunto bueno de tamaño al menos $3$ ? Versión IMO 2014/6 (adaptada). Una secuencia $a_1, \ldots, a_n$ es buena si para todo $1 \le i < j < k \le n$ , $(a_j - a_i) \nmid (a_k - a_j)$ . Determina la longitud máxima de una secuencia buena de enteros positivos no mayores que $N$ .

C3-6.4★★★★★IMO 2016 Problema 6

Sea $n \ge 3$ un entero. Llamamos buena a una secuencia $(a_1, a_2, \ldots, a_{2n})$ de enteros de $\{1, 2, \ldots, n\}$ si satisface: (i) cada $j \in \{1, \ldots, n\}$ aparece exactamente dos veces; (ii) para todo $k \in \{1, \ldots, 2n\}$ , si $a_k = a_{k'} = j$ con $k < k'$ , entonces $a_{k+1} + a_{k+2} + \cdots + a_{k'-1}$ es divisible por $j$ . Determina todos los valores de $n$ para los cuales existe una secuencia buena.

C3-6.5★★★★IMO Shortlist 2015 C4

Sean $n$ y $k$ enteros positivos con $k \le n$ . Se tiene un tablero $n \times n$ . Se quiere colocar fichas en algunas casillas de modo que en toda fila y toda columna haya exactamente $k$ fichas. Demuestra que el número de tales colocaciones es divisible por $\left(\frac{n!}{k! (n-k)!}\right)^2 \cdot \frac{k!^n}{n!}$ . Versión simplificada (nivel C4). Sean $m, n$ enteros positivos. Se tienen $mn$ objetos que deben distribuirse en una cuadrícula $m \times n$ de urnas, de modo que cada fila tenga exactamente $n$ objetos y cada columna tenga exactamente $m$ objetos (objetos distinguibles, urnas distinguibles). Demuestra que el número de distribuciones es divisible por $\frac{(mn)!}{(m!)^n (n!)^m} \cdot (m!)^n$ .

C3-6.6★★★★★IMO 2019 Problema 3

Un nociclador social es un conjunto $S$ de personas (con $|S| \ge 3$ ) tal que: para todo subconjunto $T \subseteq S$ con $|T| \ge 3$ , no todas las personas de $T$ tienen la misma cantidad de amigos en $T$ . (La amistad es simétrica: si $A$ es amigo de $B$ , entonces $B$ es amigo de $A$ .) Sea $G$ un grafo con $n$ vértices y $m$ aristas, sin lazos ni aristas múltiples, tal que el conjunto de vértices $V(G)$ es un nociclador social. Demuestra que $m \le \binom{n}{2} - n + 1$ .

C3-6.7★★★★★IMO Shortlist 2018 C4

Sea $n$ un entero positivo. Se tienen $n^2$ casillas en una cuadrícula $n \times n$ . Un ciclo monótono es un ciclo $C$ en la cuadrícula (secuencia de casillas adyacentes que regresa a la casilla inicial) tal que el ciclo es monótono: nunca retrocede en la dirección $x$ ni en la dirección $y$ . Más precisamente, un ciclo monótono de longitud $2n$ recorre $n$ pasos en direcciones no-negativas (derecha o arriba) y $n$ pasos en direcciones no-positivas (izquierda o abajo), alternando de modo que el ciclo sea una curva de Jordan discreta. Demuestra que en toda coloración de las $n^2$ casillas con $k$ colores, si $k \le n$ , existe un ciclo monótono cuyos vértices usan todos los $k$ colores.

C3-6.8★★★★★IMO 2021 Problema 6

Sea $m \ge 2$ un entero. Se consideran subconjuntos $A$ de $\{1, 2, \ldots, 2021\}$ de tamaño $m$ tales que: para todo divisor $d > 1$ de $m$ , no existen $d$ elementos de $A$ en progresión aritmética. Demuestra que el número de tales subconjuntos $A$ es par. Versión combinatoria directa. Sea $n \ge 2$ un entero y sea $\mathcal{F}$ la familia de todos los subconjuntos $m$ -elementales de $\{1, \ldots, n\}$ libres de progresiones aritméticas de longitud $\ge 3$ . Demuestra que $|\mathcal{F}|$ es par si $n$ y $m$ satisfacen ciertas condiciones de paridad.

← Lección 6.3 Lección F.1 →