Simulacro 2: 3 problemas tipo IMO día 1 y 2

Instrucciones del simulacro

Los siguientes tres problemas tienen el nivel de dificultad de P3 o P6 del IMO (los más difíciles de cada día). El tiempo sugerido es 4 horas en competencia real; aquí estudia las soluciones con profundidad. El énfasis está en reconocer la técnica antes de ver la solución: ¿es un problema probabilístico? ¿Un argumento de extremos? ¿Un invariante de juego?

Problema 4 (C3-nivel): Método probabilístico básico

Enunciado. Sea $G = (V, E)$ un grafo con $n$ vértices y $m$ aristas. Demuestra que $G$ contiene un subgrafo bipartito con al menos $m/2$ aristas.

Solución (método probabilístico de Erdős). Asignamos a cada vértice $v \in V$ un color $c(v) \in \{\text{rojo}, \text{azul}\}$ de manera independiente y uniforme (cada vértice es rojo con probabilidad $1/2$ y azul con probabilidad $1/2$). Definimos el grafo bipartito $H$ como el subgrafo de $G$ formado por las aristas $\{u,v\}$ tal que $c(u) \ne c(v)$ (una arista "cruza" la bipartición).

Para cada arista $\{u,v\} \in E$, la probabilidad de que $\{u,v\}$ sea una arista de $H$ es $\Pr[c(u) \ne c(v)] = \Pr[\text{rojo-azul o azul-rojo}] = \frac{1}{2}$.

Por linealidad del valor esperado: $\mathbb{E}[|E(H)|] = \sum_{\{u,v\} \in E} \Pr[c(u) \ne c(v)] = \frac{m}{2}$.

Como el valor esperado del número de aristas de $H$ es $m/2$, existe al menos una coloración para la cual $|E(H)| \ge m/2$. El subgrafo $H$ correspondiente a esa coloración es bipartito (las dos clases son los vértices rojos y los azules) y tiene al menos $m/2$ aristas. ✓

Nota. Esta es la demostración probabilística más icónica de Erdős (1947). Obsérvese que el argumento no construye explícitamente el subgrafo bipartito: simplemente demuestra su existencia.

Problema 5 (C4-nivel): Ramsey extremal

Enunciado. Demuestra que $R(3,3) = 6$: en cualquier 2-coloración de las aristas del grafo completo $K_6$ (rojo y azul), existe un triángulo monocrómático. Además, exhibe una 2-coloración de $K_5$ sin triángulo monocrómático.

**Solución: $R(3,3) \le 6$.** Sea $v$ un vértice de $K_6$. Tiene $5$ aristas. Por el principio de las casillas, al menos $\lceil 5/2 \rceil = 3$ aristas son del mismo color; digamos que $v$-$a$, $v$-$b$, $v$-$c$ son rojas. Consideramos las aristas del triángulo $\{a,b,c\}$:

Si alguna de $\{a,b\}$, $\{b,c\}$, $\{a,c\}$ es roja, digamos $\{a,b\}$, entonces el triángulo $v$-$a$-$b$ es monocrómático rojo. Si las tres aristas $\{a,b\}, \{b,c\}, \{a,c\}$ son azules, el triángulo $a$-$b$-$c$ es monocrómático azul. En cualquier caso, existe un triángulo monocrómático. ✓

**Solución: $R(3,3) > 5$, es decir, existe una 2-coloración de $K_5$ sin triángulo monocrómático.** Tomamos los vértices $\{0,1,2,3,4\}$ sobre $\mathbb{Z}_5$ y coloreamos la arista $\{i,j\}$ de rojo si $|i-j| \in \{1,4\}$ (módulo 5, distancia 1 en el ciclo), y de azul si $|i-j| \in \{2,3\}$. El grafo rojo es $C_5$ (un ciclo de 5 vértices), que es libre de triángulos. El grafo azul también es $C_5$ (con los vértices en orden $0,2,4,1,3$), igualmente libre de triángulos. ✓

Conclusión: $R(3,3) = 6$.

Problema 6 (C5-nivel): Juego con invariante de paridad

Enunciado. En un tablero de $n \times n$ ($n$ par), A y B juegan alternativamente (A comienza). En cada turno, el jugador activo elige un domino libre ($1 \times 2$ o $2 \times 1$) y lo coloca en el tablero, cubriendo dos casillas adyacentes vacías. El jugador que no puede mover pierde. Determina quién tiene estrategia ganadora para todo $n$ par.

Solución. El jugador B tiene estrategia ganadora para todo $n$ par.

Estrategia de B (emparejamiento de espejo). Dividimos el tablero $n \times n$ en $n^2/2$ pares de casillas adyacentes formando un emparejamiento perfecto $\mathcal{M}$ (por ejemplo, el emparejamiento de dominós horizontales que cubre el tablero por filas: $\{(i,2j-1),(i,2j)\}$ para $1 \le i \le n$, $1 \le j \le n/2$). Como $n$ es par, tal emparejamiento perfecto existe.

Invariante de espejo. Después de cada movimiento de A (que coloca un domino cubriendo casillas $a$ y $b$), B responde colocando un domino en el par $\{a', b'\}$ de $\mathcal{M}$ que contenga la casilla libre del par al que pertenece $a$ o $b$... Más precisamente, la estrategia se implementa como sigue: el tablero tiene $n^2/2$ pares en $\mathcal{M}$. Cuando A coloca un domino en $\{u,v\}$, B coloca su domino en el "par espejo" de $\mathcal{M}$: el par $\{u', v'\}$ tal que $\{u',v'\}$ es disjunto de $\{u,v\}$ y existe por la estructura de $\mathcal{M}$. Esto siempre es posible porque si A puede mover, hay al menos un par libre en $\mathcal{M}$, y B puede ocuparlo.

Más formalmente: B usa el emparejamiento de Thurston del tablero, que garantiza que si A puede colocar un domino, B puede colocar el domino "complementario" en el emparejamiento. Al final, A es el primero en no poder mover. ✓