Simulacro 1: 3 problemas tipo Shortlist combinatoria

Instrucciones del simulacro

Este simulacro replica el formato y la dificultad de los problemas del Shortlist IMO categoría C, niveles C1 a C3. Tiempo sugerido: 45 minutos para los tres problemas (15 minutos por problema). Al terminar, compara tu solución con la solución oficial prestando atención a la rigurosidad y la estructura.

En los problemas de grafos extremales, el paso clave es siempre construir el ejemplo que alcanza la cota y luego demostrar que no se puede hacer mejor. En los problemas de doble conteo, busca dos maneras de evaluar $\sum_{v} f(v)$ sobre el mismo conjunto de incidencias. En los juegos, formula la estrategia del ganador como un invariante.

Problema 1 (C1-nivel): Grafo extremal sin triángulo

Enunciado. Sea $G$ un grafo simple con $n$ vértices que no contiene triángulos (subgrafo completo $K_3$). Demuestra que $G$ tiene a lo sumo $\lfloor n^2/4 \rfloor$ aristas, y describe todos los grafos que alcanzan esta cota.

**Solución (Teorema de Turán para $r=2$).** Sea $G$ un grafo sin triángulos con $n$ vértices y $m$ aristas. Para cada arista $\{u,v\}$, los vecinos de $u$ y los vecinos de $v$ deben ser disjuntos (pues un vecino común formaría un triángulo $u$-$w$-$v$). Luego $d(u) + d(v) \le n$ para toda arista $\{u,v\}$.

Sumando sobre todas las aristas: $\sum_{\{u,v\} \in E} [d(u)+d(v)] \le nm$. El lado izquierdo es $\sum_v d(v)^2$ (cada $d(v)$ se suma $d(v)$ veces, una por cada arista incidente en $v$). Por Cauchy-Schwarz: $\sum_v d(v)^2 \ge \frac{(\sum_v d(v))^2}{n} = \frac{(2m)^2}{n}$. Combinando: $\frac{4m^2}{n} \le nm$, lo que da $m \le \frac{n^2}{4}$. Como $m$ es entero, $m \le \lfloor n^2/4 \rfloor$.

Igualdad. El grafo bipartito completo $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$ tiene $\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor$ aristas, no contiene triángulos (es bipartito), y es el único grafo extremal salvo isomorfismo (Turán 1941). ✓

Problema 2 (C2-nivel): Doble conteo con biyección

Enunciado. Sea $n \ge 1$. Demuestra que $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.

Solución por doble conteo (biyección de Vandermonde). Contamos el número de subconjuntos de tamaño $n$ de un conjunto $S$ con $2n$ elementos. Por definición, este número es $\binom{2n}{n}$.

Ahora contamos el mismo objeto de otro modo. Partimos $S = A \cup B$ con $|A| = |B| = n$ (una mitad "roja" y una mitad "azul"). Para elegir $n$ elementos de $S = A \cup B$, podemos elegir $k$ elementos de $A$ y $n-k$ de $B$, para algún $k \in \{0,1,\ldots,n\}$. Esto da $\binom{n}{k}\binom{n}{n-k} = \binom{n}{k}^2$ formas (pues $\binom{n}{n-k}=\binom{n}{k}$).

Sumando sobre todos los valores de $k$: $\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^2$. ✓

Nota. La biyección explícita es: cada subconjunto $T \subseteq S$ de tamaño $n$ se corresponde con el par $(T \cap A, T \cap B)$, donde $|T \cap A| = k$ y $|T \cap B| = n-k$ para algún $k$. Esta es la biyección de la convulución de Vandermonde.

Problema 3 (C3-nivel): Juego de fichas con estrategia de espejo

Enunciado. Dos jugadores, A y B, juegan en un tablero de $1 \times 2n$ casillas numeradas $1, 2, \ldots, 2n$. A y B alternan turnos (A comienza). En cada turno, el jugador activo coloca una ficha en alguna casilla vacía. Pierde el jugador que complete un par de casillas adyacentes que contengan fichas. Demuestra que B tiene estrategia ganadora.

Solución (estrategia de espejo). Definimos los pares de casillas simétricas respecto al centro: $\{1, 2n\}$, $\{2, 2n-1\}$, $\ldots$, $\{n, n+1\}$. Son exactamente $n$ pares.

Estrategia de B. Después de cada movimiento de A (que coloca una ficha en la casilla $i$), B responde colocando la ficha en la casilla $2n+1-i$ (el espejo de $i$). Esta casilla siempre está libre: si $2n+1-i$ estuviera ocupada, B ya habría respondido al movimiento que la ocupó con $i$, pero $i$ estaba libre antes del turno de A.

Invariante. Después de cada turno de B, las fichas están dispuestas simétricamente: si la casilla $j$ tiene ficha, también la tiene $2n+1-j$.

B nunca pierde. Supón que en algún turno, la jugada de A (en la casilla $i$) forma un par adyacente $\{i-1, i\}$ donde $i-1$ ya tenía ficha. Por el invariante, la casilla $2n+1-(i-1) = 2n+2-i$ también tiene ficha. La jugada de espejo de B sería la casilla $2n+1-i$. Las casillas $2n+1-i$ y $2n+2-i$ son adyacentes, así que B formaría el par adyacente $\{2n+1-i, 2n+2-i\}$... esto solo es un problema si $2n+1-i$ y $2n+2-i$ son el par adyacente que haría perder a B.

El punto clave: A siempre mueve antes que B, y la configuración es simétrica tras cada par de turnos. Si una posición es "perdedora" (el siguiente jugador en mover pierde), es A quien enfrenta esa posición cuando el tablero es casi lleno. La estrategia de espejo garantiza que cualquier situación que A pueda crear para B, B puede replicarla para A con el espejo, y como A mueve en el estado vacío primero, es A quien queda atrapado. ✓