Simulacro 2: 3 problemas tipo Iberoamericana

Instrucciones del simulacro

Este simulacro replica el formato y la dificultad de los problemas de combinatoria P2–P3 de la Olimpiada Iberoamericana de Matemáticas (IbAm). Tiempo sugerido: 60 minutos (20 minutos por problema).

Los problemas de nivel IbAm tienen una idea clave que, una vez identificada, hace la solución fluir de manera natural. La dificultad radica en encontrar esa idea. Si estás atascado: (a) prueba con $n = 3, 4, 5$; (b) busca una bipartición o coloración oculta; (c) considera si el problema pide existencia (→ Hall) o una cantidad (→ PIE/doble conteo).

Una solución IbAm bien redactada tiene exactamente tres partes: definición de los objetos, construcción o verificación de la propiedad clave, y conclusión. Practica escribir con esa estructura.

Problema 1 (Grafos — Matching/Coloración): Índice cromático

Problema F2-A (estilo IbAm 2018). Sea $G$ un grafo bipartito con partes $A$ y $B$, $|A| = |B| = n$, en el que todo vértice tiene grado exactamente $k$ (con $1 \leq k \leq n$). Demuestra que las aristas de $G$ pueden colorearse con $k$ colores de modo que aristas del mismo color no comparten un vértice (es decir, el índice cromático de aristas $\chi'(G) = k$).

Solución. Demostramos por inducción en $k$.

**Base $k = 1$:** El grafo es 1-regular, así que es un matching perfecto (pues $|A| = |B| = n$ y cada vértice tiene grado 1). Un matching perfecto es directamente una coloración con 1 color. $\checkmark$

Paso inductivo: Supongamos que todo grafo bipartito $n \times n$ con todos los grados iguales a $k-1$ tiene índice cromático $k-1$. Sea $G$ un grafo bipartito $k$-regular con $|A| = |B| = n$.

Por el teorema de Hall aplicado a grafos bipartitos regulares, $G$ tiene un matching perfecto $M$. (Verificación: para cualquier $S \subseteq A$, el doble conteo da $k|S| \leq k|N(S)|$, luego $|N(S)| \geq |S|$; por Hall existe matching perfecto.)

El grafo $G' = G \setminus M$ (quitamos las aristas de $M$) tiene todos los grados iguales a $k-1$ (pues cada vértice pierde exactamente una arista, la del matching perfecto). Por hipótesis inductiva, $G'$ tiene una coloración de aristas con $k-1$ colores.

Coloreamos las aristas de $M$ con el color $k$. La coloración de $G'$ con $k-1$ colores más el color $k$ para las aristas de $M$ da una coloración de $G$ con $k$ colores donde aristas del mismo color no comparten vértice (las aristas de $M$ son un matching, luego no comparten vértice; las aristas de $G'$ están correctamente coloreadas). Por tanto $\chi'(G) \leq k$. Como $G$ tiene vértices de grado $k$, necesariamente $\chi'(G) \geq k$, luego $\chi'(G) = k$. $\square$

Problema 2 (Conteo con restricciones): Permutaciones con distancia acotada

Problema F2-B (estilo IbAm 2016). Sea $n \geq 2$ un entero. Llamamos $f(n)$ al número de permutaciones $\sigma$ de $\{1, 2, \ldots, n\}$ tales que $|\sigma(i) - i| \leq 1$ para todo $i \in \{1, \ldots, n\}$ (cada elemento se desplaza a lo sumo una posición). Demuestra que $f(n) = F_{n+1}$ donde $F_k$ es el $k$-ésimo número de Fibonacci ($F_1 = F_2 = 1$, $F_{k} = F_{k-1} + F_{k-2}$).

Solución. Analizamos la estructura de las permutaciones con $|\sigma(i) - i| \leq 1$. Esto significa que $\sigma(i) \in \{i-1, i, i+1\} \cap \{1, \ldots, n\}$. En particular, $\sigma(i)$ es $i-1$, $i$, o $i+1$.

Observación clave: si $\sigma(i) = i+1$, como $\sigma$ es biyectiva, el elemento $i+1$ ya está en la posición $i$, y la posición $i+1$ debe recibir algún valor. Como $\sigma(i+1) \in \{i, i+1, i+2\}$, y $i+1$ ya fue usado, $\sigma(i+1) \in \{i, i+2\}$. Si $\sigma(i+1) = i$, entonces el par $(i, i+1)$ se intercambia: $\sigma(i) = i+1$ y $\sigma(i+1) = i$ (una transposición de elementos adyacentes). Si $\sigma(i+1) = i+2$, entonces continuamos la cadena.

En realidad, la permutación $\sigma$ con $|\sigma(i) - i| \leq 1$ se descompone en: (a) puntos fijos ($\sigma(i) = i$) y (b) transposiciones de elementos adyacentes ($\sigma(i) = i+1$ y $\sigma(i+1) = i$). No puede haber ciclos de longitud $\geq 3$ (si $\sigma(i) = i+1$ y $\sigma(i+1) = i+2$, entonces $\sigma(i+1) = i+2$ y necesitamos $\sigma(i+2) \in \{i+1, i+2, i+3\}$; si $\sigma(i+2) = i+1$, pero $i+1$ ya fue imagen de $i$, contradicción. Si $\sigma(i+2) = i+2$, entonces el ciclo sería $(i, i+1)$ y $i+2$ fijo, no hay ciclo de longitud 3. Si $\sigma(i+2) = i+3$, continuamos, pero en algún punto debe cerrarse el ciclo sin usar elementos ya asignados; esto lleva a ciclos solo de longitud 2.).

Por tanto, $\sigma$ es un producto de transposiciones de elementos adyacentes no solapadas y puntos fijos. Equivalentemente, $\sigma$ corresponde a una selección de un subconjunto de pares $\{(1,2), (2,3), \ldots, (n-1,n)\}$ que son no adyacentes (no comparten un índice), y los demás elementos son puntos fijos.

El número de tales selecciones satisface la recurrencia: sea $f(n)$ el número de permutaciones válidas de $[n]$. Al considerar el elemento $n$: o bien $\sigma(n) = n$ (punto fijo) y el resto es una permutación válida de $[n-1]$, dando $f(n-1)$ opciones; o bien $\sigma(n) = n-1$ y $\sigma(n-1) = n$ (transposición $(n-1, n)$) y el resto es una permutación válida de $[n-2]$, dando $f(n-2)$ opciones. Luego $f(n) = f(n-1) + f(n-2)$ con $f(1) = 1$ ($\sigma = (1)$) y $f(2) = 2$ ($\sigma = (1,2)$ o $(2,1)$). Esta es exactamente la recurrencia de Fibonacci con $f(1) = F_2 = 1$ y $f(2) = F_3 = 2$, luego $f(n) = F_{n+1}$. $\square$

Problema 3 (Combinatoria geométrica): Puntos en posición general

Problema F2-C (estilo IbAm 2020). Se tienen $2n$ puntos en el plano en posición general (no tres colineales). Se colorean $n$ de ellos de rojo y $n$ de azul. Demuestra que existe una recta que separa los puntos rojos de los azules (es decir, todos los rojos quedan de un lado y todos los azules del otro) si y solo si no existe ningún segmento entre un punto rojo y uno azul que contenga en su interior a otro punto del conjunto.

Nota: Esta versión pide demostrar la existencia de una recta separadora bajo una condición específica. Probamos la dirección "si existe la recta separadora, entonces no hay segmento rojo-azul con puntos internos" (la más directa) y comentamos la dirección contraria.

Solución (dirección ⟹). Supongamos que existe una recta $\ell$ que separa los rojos de los azules. Sea $s = \overline{PQ}$ un segmento con $P$ rojo y $Q$ azul. Como $P$ y $Q$ están en lados opuestos de $\ell$, el segmento $\overline{PQ}$ cruza a $\ell$ en un punto $X$ interior. Como $X \in \ell$ y los $2n$ puntos están en posición general (ninguno sobre $\ell$, pues $\ell$ los separa), $X$ no es ninguno de los $2n$ puntos. Luego el interior del segmento $\overline{PQ}$ no contiene puntos del conjunto. $\square$

Dirección ⟸ (bosquejo). Si ningún segmento rojo-azul contiene puntos del conjunto en su interior, podemos construir la recta separadora de manera constructiva. Consideramos la envoltura convexa de los puntos rojos y la envoltura convexa de los puntos azules. La condición sobre los segmentos implica que estas dos envoltura son disjuntas (si se intersectaran, habría un punto de intersección que sería interior a algún segmento rojo-azul). Por el teorema de separación de conjuntos convexos, dos conjuntos convexos compactos disjuntos pueden separarse por una recta. $\square$