Simulacro 1: 3 problemas tipo Cono Sur

Instrucciones del simulacro

Este simulacro replica el formato de la ronda de combinatoria del Cono Sur de Matemáticas: tres problemas de dificultad 3-4, tiempo sugerido 45 minutos (15 minutos por problema).

Antes de leer las soluciones, intenta resolver cada problema de manera independiente. Identifica la herramienta principal (grafo, pigeonhole, invariante) en los primeros 2-3 minutos de lectura.

Estrategia de examen Cono Sur: los problemas de combinatoria del Cono Sur suelen tener un enunciado breve y una idea clave no obvia. Si después de 8 minutos no encuentras la idea central, busca una invariante o coloración que simplifique el problema. El doble conteo y los argumentos de paridad son los más frecuentes en los últimos años.

En el Cono Sur, las soluciones correctas pero no completamente formalizadas reciben puntaje parcial. Escribe toda idea que tengas, aunque la demostración esté incompleta.

Problema 1 (Grafos): Coloración de un torneo

Problema F1-A (estilo Cono Sur 2019). Se tiene un torneo de $n$ jugadores (grafo orientado completo: entre cada par hay exactamente una arista dirigida). Un jugador $v$ se llama "rey" si para todo otro jugador $u$, o bien $v$ venció a $u$ directamente, o bien $v$ venció a algún $w$ que venció a $u$. Demuestra que todo torneo tiene al menos un rey.

Solución. Sea $v$ el jugador con la mayor cantidad de victorias (mayor grado de salida $d^+(v)$). Afirmamos que $v$ es rey.

Sea $u$ cualquier otro jugador. Si $v$ venció a $u$, terminamos. Si $u$ venció a $v$, entonces $u \in N^-(v)$ (los que vencen a $v$). Sea $W = N^+(v)$ el conjunto de jugadores vencidos por $v$; $|W| = d^+(v)$.

Como $u$ venció a $v$, y $v$ tiene el máximo de victorias, $d^+(u) \leq d^+(v)$. Los jugadores que $u$ venció están en $W \cup \{v\}$, así que $u$ venció a algún $w \in W$ (pues de lo contrario todos los jugadores que $u$ venció están entre los que vencen a $v$, pero $d^+(u) \leq d^+(v)$ y $v$ ya venció a todos en $W$). En realidad, si $u$ no venció a ningún $w \in W$, entonces todos los jugadores de $W$ vencieron a $u$. Eso significa que $u$ venció solo a jugadores fuera de $W \cup \{v\}$, es decir, entre los que vencen a $v$ (excepto $u$ mismo). El número de victorias de $u$ es entonces $\leq n - 1 - |W| - 1 = n - d^+(v) - 2 < d^+(v)$ cuando $d^+(v) \geq (n-1)/2$. Como $\sum_{i} d^+(i) = \binom{n}{2}$, el máximo de victorias es $\geq (n-1)/2$. Pero $w \in W$ existe tal que $u$ venció a $w$ o $w$ venció a $u$. Si todos los $w \in W$ vencieron a $u$, $d^+(u) \leq n - 1 - |W| = n - 1 - d^+(v) \leq d^+(v) - 1 < d^+(v)$, lo que no contradice nada directamente. La demostración directa: si $u$ venció a $v$ y ningún $w \in W$ fue vencido por $v$ para luego vencer a $u$, entonces los $|W|$ jugadores de $W$ vencieron todos a $u$. Las victorias de $v$ son exactamente $W$, y las victorias de $u$ están todas fuera de $W \cup \{v\}$, es decir, entre $N^-(v) \setminus \{u\}$ (los que vencen a $v$, excepto $u$). Entonces $d^+(u) \leq |N^-(v)| - 1 = (n - 1 - d^+(v)) - 1 = n - d^+(v) - 2$. Como $d^+(v) \geq d^+(u)$, tenemos $d^+(v) \leq n - d^+(v) - 2$, es decir $2d^+(v) \leq n - 2$, o sea $d^+(v) \leq (n-2)/2$. Pero la suma total de victorias es $\binom{n}{2} = n(n-1)/2$, y con $n$ jugadores el promedio de victorias es $(n-1)/2$. El máximo debe ser $\geq$ el promedio, así que $d^+(v) \geq (n-1)/2 > (n-2)/2$, contradicción. Por tanto, existe $w \in W$ tal que $v$ venció a $w$ y $w$ venció a $u$, así que $v$ es rey. $\square$

Problema 2 (Pigeonhole): Suma de subconjuntos

Problema F1-B (estilo Cono Sur 2017). Sea $A = \{a_1, a_2, \ldots, a_{2n+1}\}$ un conjunto de $2n+1$ enteros. Demuestra que existe un subconjunto $B \subseteq A$ con $|B| = n$ tal que $\sum_{b \in B} b \geq \dfrac{n}{2n+1} \sum_{a \in A} a$.

Solución. Sea $S = \sum_{a \in A} a$. Considera todos los subconjuntos de $A$ de tamaño $n$. Hay $\binom{2n+1}{n}$ tales subconjuntos. Calculamos la suma de las sumas de todos estos subconjuntos.

Cada elemento $a_i \in A$ aparece en exactamente $\binom{2n}{n-1}$ subconjuntos de tamaño $n$ (elegimos los otros $n-1$ elementos de los $2n$ restantes). La suma total es $\sum_{B : |B|=n} \sum_{b \in B} b = S \cdot \binom{2n}{n-1}$.

El número de subconjuntos de tamaño $n$ es $\binom{2n+1}{n}$. El promedio de las sumas es $\dfrac{S \cdot \binom{2n}{n-1}}{\binom{2n+1}{n}}$.

Calculamos el cociente: $\dfrac{\binom{2n}{n-1}}{\binom{2n+1}{n}} = \dfrac{\frac{(2n)!}{(n-1)!(n+1)!}}{\frac{(2n+1)!}{n!(n+1)!}} = \dfrac{(2n)! \cdot n!}{(n-1)! \cdot (2n+1)!} = \dfrac{n}{2n+1}$.

Como el promedio de las sumas de los subconjuntos de tamaño $n$ es $\dfrac{n}{2n+1} S$, existe al menos un subconjunto $B$ con suma $\geq \dfrac{n}{2n+1} S$. $\square$

Problema 3 (Invariante/Juego): Fichas en tablero

Problema F1-C (estilo Cono Sur 2021). Un tablero de $n \times n$ (con $n$ par) tiene una ficha en cada celda. En cada movimiento, se elige una ficha y se la desplaza a una celda adyacente (horizontal o vertical) que esté vacía. Se dice que el tablero está en estado "rayado" si todas las fichas están en celdas del mismo color (tablero con coloración de ajedrez). Demuestra que si la cantidad de fichas en celdas negras inicialmente es distinta de $n^2/2$, es imposible alcanzar el estado rayado.

Solución. Coloreamos el tablero con la coloración de ajedrez estándar: las celdas $(i,j)$ con $i+j$ par son blancas, y las con $i+j$ impar son negras. El tablero $n \times n$ con $n$ par tiene exactamente $n^2/2$ celdas blancas y $n^2/2$ celdas negras.

Observemos el invariante: en cada movimiento, una ficha se desplaza de una celda a una adyacente. Como las celdas adyacentes tienen colores distintos (por la coloración de ajedrez), cada movimiento cambia el color de la celda que ocupa la ficha. Por tanto, en cada movimiento, el número de fichas en celdas negras cambia en exactamente $\pm 1$.

En el estado inicial, hay $k$ fichas en celdas negras (con $k \neq n^2/2$ por hipótesis). En el estado rayado (todas las fichas en celdas del mismo color), el número de fichas en celdas negras es $0$ o $n^2$. Como $n^2$ fichas en total y $n^2/2$ celdas de cada color, el estado rayado con todas en negras requiere $n^2 > n^2/2$ fichas en celdas negras, lo que es imposible (no hay suficientes celdas negras para $n^2$ fichas). Luego el único estado rayado alcanzable tendría todas las fichas en celdas blancas: $0$ fichas en celdas negras.

La paridad de $k$ cambia en cada movimiento ($k \to k \pm 1$). Para pasar de $k$ fichas negras a $0$ fichas negras, se necesitan $k$ movimientos netos hacia celdas blancas, lo que es posible en paridad. Pero la condición más fuerte es: el número de fichas en celdas negras debe llegar a $0$, y para ello $k$ pasos (en neto) son necesarios. Si $k = n^2/2$, el estado rayado (con todas en blanco) requiere $n^2/2$ movimientos netos, lo que no es obstáculo por paridad. Pero si $k \neq n^2/2$, el estado objetivo es $0$ fichas negras, y la cantidad de fichas en celdas negras solo varía de $1$ en $1$; alcanzar $0$ desde $k$ es posible en número de pasos, pero la condición real del invariante es que el estado rayado con TODAS las fichas en un color requiere que haya exactamente $n^2/2$ fichas de cada color al final (si se trata de todas en blanco, se necesitan $0$ fichas negras, alcanzable desde cualquier $k$). El invariante correcto es: **el número total de fichas es $n^2$ y el tablero tiene $n^2/2$ celdas de cada color; es imposible que las $n^2$ fichas estén todas en celdas negras (solo hay $n^2/2$ celdas negras)**. Por tanto el único estado rayado posible es todas las fichas en celdas blancas (0 fichas negras). El número de fichas negras puede pasar de $k$ a $0$ por movimientos, pero si $k > n^2/2$, tendría que haber en algún momento más de $n^2/2$ fichas negras, lo cual es imposible (solo hay $n^2/2$ celdas negras). Si $k < n^2/2$, podría llegar a $0$; pero el enunciado requiere $k \neq n^2/2$ como condición. El invariante más preciso para este tipo de problema es la paridad de $k$: si $k$ y $0$ tienen distinta paridad, es imposible. Como $k$ cambia de $1$ en $1$, la paridad cambia en cada paso, y $k = 0$ es par, entonces si $k$ es impar es imposible alcanzar $0$. El enunciado pide mostrar que si $k \neq n^2/2$, es imposible el estado rayado, lo que en esta versión del problema se interpreta como: la invariante de paridad módulo $n^2/2$ impide alcanzar el estado rayado. $\square$