Colección regional-nacional: grafos, conteo doble y argumentos extremales

Problema 1: modela el torneo como $K_8$ ($28$ aristas = partidas), donde cada día es un emparejamiento perfecto ($4$ aristas). Tras $5$ días se han jugado $20$ partidas; las $8$ restantes (días $6$ y $7$) forman un grafo $2$-regular en $8$ vértices, que solo puede ser un único ciclo $C_8$ o dos ciclos $C_4$ disjuntos (¿por qué no puede tener ciclos de longitud $2$ ni impares?). En cualquiera de los dos casos, encuentra $4$ vértices tales que los $\binom{4}{2}=6$ pares entre ellos NO sean aristas de ese grafo $2$-regular: esos $4$ jugadores ya han jugado entre sí todas las partidas.

Problema 2: supón que hay $31$ comités y cuenta los pares (miembro, comité al que pertenece): hay $31\times5=155$ de estos pares repartidos entre $25$ miembros, así que por el principio del palomar algún miembro pertenece a al menos $7$ comités. Mira esos $7$ comités: entre ellos hay $7\times4=28$ "asientos" para los otros $24$ miembros, y vuelve a aplicar el palomar para encontrar dos comités (de esos $7$) que comparten un segundo miembro además del original.

Problema 3: empieza por el caso plano: si $A_n$ es el número de contactos en un piso triangular de $n$ filas de esferas, comprueba que $A_n=A_{n-1}+3(n-1)$. Para el tetraedro completo, al añadir el piso $n$-ésimo (con $A_n$ contactos internos) se generan además los contactos entre ese piso y el piso $n-1$, que son $3\binom{n}{2}$. Plantea y resuelve la recurrencia resultante para $C_n$ en función de $C_{n-1}$, y comprueba que la solución es $C_n=n^3-n$.

Problema 4: traduce la hipótesis al lenguaje de grafos: si $H$ es el grafo cuyas aristas son los pares de enemigos, la condición dice exactamente que $H$ no tiene triángulos (ningún vértice tiene dos vecinos en $H$ que sean a su vez vecinos entre sí). Recuerda el hecho clásico de que en cualquier grafo con $n\geq2$ vértices existen dos vértices del mismo grado (los $n$ grados posibles van de $0$ a $n-1$, pero $0$ y $n-1$ no pueden coexistir). Si esos dos vértices de igual grado en $H$ no son adyacentes, ya tienes la pareja $X,Y$; si lo son, usa que $H$ es libre de triángulos para acotar sus grados y reduce el problema a un conjunto más pequeño de personas.

Problema 5: considera la agrupación extremal: ordena los valores de las bolas de forma no creciente $a_1\geq a_2\geq\cdots\geq a_{2n}$ y forma las parejas consecutivas $(a_1,a_2),(a_3,a_4),\ldots$. Sus sumas $s_1\geq s_2\geq\cdots\geq s_n$ quedan automáticamente ordenadas, así que si dos de ellas coinciden (como garantiza la hipótesis aplicada a esta pareja particular), deben ser consecutivas: $s_k=s_{k+1}$, es decir $a_{2k-1}+a_{2k}=a_{2k+1}+a_{2k+2}$ con $a_{2k-1}\geq a_{2k}\geq a_{2k+1}\geq a_{2k+2}$. ¿Qué fuerza esto sobre los cuatro valores?

Problema 6: para (b), aplica un argumento extremal e iterativo: con $6$ fichas repartidas en $4$ columnas, por el palomar alguna columna contiene al menos $2$ fichas; elimínala. Quedan a lo sumo $4$ fichas en las $3$ columnas restantes, así que de nuevo alguna columna tiene al menos $2$; elimínala también. Las fichas restantes (a lo sumo $2$) se eliminan con dos filas. Para (a), experimenta colocando $7$ fichas de modo que ninguna fila ni columna concentre demasiadas, y comprueba a mano que ningún par de filas junto con un par de columnas cubre las $7$ — exhibir esa configuración basta.

Problema 7: supón que el punto $P$ es negro y que su fila contiene $k$ puntos negros; la condición de equilibrio obliga a que su columna también contenga exactamente $k$ puntos negros. Toma un punto negro cuya fila tenga el número máximo de puntos negros entre todos los puntos negros, y razona de forma extremal sobre cuántas filas y columnas pueden alcanzar ese máximo — esto te llevará a que $m$ y $n$ deben cumplir $n=m$, $n=2m$ o $m=2n$.

Problema 8: analiza primero los casos pequeños $n=1,2,3,4$: con $4$ piedras, el jugador en turno puede coger la mitad ($2$) y dejar al rival exactamente con $2$, ganando dos turnos después. A partir de ahí, comprueba que un jugador que se encuentra con un número par $n>4$ puede coger $1$ piedra (dejando un impar al rival, que está obligado a coger $1$), de modo que dos turnos después vuelve a tener un par menor — itera este proceso hasta llegar a $4$ piedras en tu propio turno.

Problema 9: cada jugador debe enfrentarse a los otros $p^2-1$ jugadores, repartidos en partidas de $p-1$ rivales cada una, lo que da una cota inferior de $p+1$ rondas. Para construir un torneo con exactamente $p+1$ rondas, representa a cada jugador como un par $(a,b)$ con $a,b\in\{0,\ldots,p-1\}$. En la ronda $k$ (para $k=0,\ldots,p-1$), agrupa a los jugadores según el valor de $a+kb \pmod p$; añade una ronda extra agrupando según el valor de $b$. Comprueba, usando que $p$ es primo, que cada par de jugadores coincide en exactamente una de estas $p+1$ rondas — es la construcción de un plano afín de orden $p$.

Problema 10: si en cada vértice concurren $g$ aristas, una coloración buena puede pintar como máximo una fracción $\frac{g-1}{g}$ de las aristas totales (en cada vértice debe quedar al menos una sin pintar). Calcula esta cota para los cinco poliedros regulares y, para cada uno, intenta alcanzarla con una coloración que además sea completamente buena. Para el octaedro y el icosaedro, suma —sobre todas las caras— el número de aristas rojas por cara y deduce, por paridad, que alguna cara debe quedar completamente roja si se alcanza el máximo de la coloración buena.

Problema 11: llama monocroma a una arista cuyos dos extremos tienen el mismo color. Para cada cara, cuenta cuántas de sus tres aristas son monocromas: si la cara es extremeña, ninguna lo es; si no lo es, el número de aristas monocromas en ella es impar ($1$ o $3$). Suma este conteo sobre todas las caras del poliedro: como cada arista pertenece exactamente a dos caras, esta suma total es par. Deduce que el número de caras NO extremeñas es par, y combina esto con el hecho de que el número total de caras de un poliedro triangulado es siempre par (usa $3F=2E$).

Problema 12: cuenta en su lugar los subconjuntos que NO son orensanos: el conjunto vacío, los $2019$ subconjuntos de un solo elemento, y los subconjuntos formados por enteros consecutivos (un "bloque"), que están determinados biunívocamente por su mínimo y su máximo — hay $\binom{2019}{2}$ de estos. Resta estos casos del total $2^{2019}$.

Problema 13: toma $m=n-1$ en la condición: como $a_1+\cdots+a_{n-1}=\frac{n(n+1)}{2}-a_n$, la divisibilidad por $n-1$ se traduce en una congruencia sencilla sobre $a_n$ módulo $n-1$. Combínala con la condición para $m=n-2$ para descartar los valores intermedios y concluir que $a_n\in\{1,n\}$. En cada uno de los dos casos, comprueba que la permutación de las $n-1$ posiciones restantes (tras un reajuste de valores) sigue cumpliendo exactamente las mismas condiciones para $n-1$, lo que da la recurrencia $|P_n|=2|P_{n-1}|$.

Problema 14: para cada posición, define su valoración como (blancas a su izquierda) + (negras a su derecha), y comprueba que intercambiar dos fichas adyacentes cambia el número de fichas equilibradas en $0$ o en $\pm2$ — es decir, no altera su paridad. Esto te permite, sin cambiar la paridad de la respuesta, llevar todas las fichas negras al principio de la fila y todas las blancas al final. En esa configuración, representa la fila como un camino en una retícula y cuenta directamente cuántas fichas son equilibradas.

Problema 15: para la primera parte, busca una coloración periódica (por bloques de tamaño creciente) que evite que $z=8(x+y)$ tenga el mismo color que $x$ e $y$ en el rango $1,\ldots,2017$. Para la segunda, parte de la observación de que tomando $x=y$ se obtiene $z=16x$: si $x$, $16x$ y $256x$ caben en $\{1,\ldots,n\}$, su coloración está muy restringida. Combina esta cadena de razón $16$ con la ecuación general (con $x\neq y$) para acotar cuántos elementos puede tener cada clase de color antes de que el palomar fuerce una solución monocromática.

Problema 16: para (a), construye un orden de eliminación: en cada paso, retira un estudiante con a lo sumo $100$ amigos dentro del subconjunto restante (existe por hipótesis), obteniendo un orden $1,\ldots,2022$. Asigna grupos de atrás hacia adelante: a cada estudiante dale el primer grupo, de entre $101$ disponibles, que no use ninguno de sus amigos ya asignados (con números mayores) — como tiene a lo sumo $100$ de esos amigos, siempre hay un grupo libre. Para ver que $100$ grupos no bastan, busca una configuración con $100$ estudiantes amigos de todos los demás. Para (b), usa la misma estrategia de eliminación: acota cuántas amistades se "eliminan" en cada paso (a lo sumo $100$, o menos cuando quedan pocos estudiantes) y suma estas cotas.

Problema 17: para cada $n=1,\ldots,202$, considera la "frontera" entre la casilla $n$ y la casilla $n+1$: el número neto de fichas que debe cruzarla es exactamente $n$. Si escribes $n=20k+r$ con $0\leq r<20$, calcula el número mínimo de movimientos (individuales o de bloques de $20$) necesarios para lograr ese cruce neto, distinguiendo según convenga compensar con movimientos en sentido contrario. Suma estos mínimos para $n=1,\ldots,202$: si el resultado es exactamente $2023$, cada frontera debe alcanzar su mínimo — analiza qué implica esto para la frontera $n=11$.

Problema 18: colorea las casillas de $S$ como un tablero de ajedrez (blancas y negras): cada saltamontes que parte de una casilla blanca llega a una negra, y viceversa, así que el movimiento se descompone en dos partes independientes. Comprueba que los movimientos de los saltamontes que parten de casillas blancas determinan, de forma biyectiva, una teselación de $S$ por fichas de dominó (cada dominó conecta la casilla de partida con la de llegada); lo mismo ocurre, independientemente, con los que parten de casillas negras. Concluye que (disposiciones asturianas) está en biyección con (pares de teselaciones de $S$ por dominós), y que por tanto su número es (número de teselaciones de $S$)$^2$.