Colección de iniciación — Conteo, palomar e invariantes

Colección de problemas de iniciación en combinatoria, todos extraídos de exámenes reales de la Olimpiada Matemática de Galicia (OMG), la Fase Local de la OME y la Fase Nacional. Antes de empezar conviene tener fresco el repaso de principios-conteo, el palomar y los invariantes-y-coloracion: la mayoría de los problemas se resuelven con una combinación sencilla de estas tres ideas, y el reto está en reconocer cuál usar primero.

1. (OMG 2002/P2) La suma de las edades de los $120$ estudiantes que se inscribieron el año pasado en Galicia en la Olimpiada Matemática era igual a $2002$ años. Demuestra que se podrían haber elegido $3$ de ellos de modo que la suma de sus edades no fuera menor que $51$ años.

2. (OMG 2002/P6) Considera $7$ puntos arbitrarios del plano y los $21$ segmentos que los conectan dos a dos. Demuestra que al menos $3$ de estos $21$ segmentos tienen longitudes distintas entre sí.

3. (OMG 1999/P3) Se consideran seis puntos en el espacio, de manera que no haya tres de ellos en una misma recta ni cuatro en un mismo plano. Si unimos cada par de puntos mediante un segmento, ¿cuántos triángulos se forman? Estos segmentos se pintan, cada uno, de color verde o de color azul. Demuestra que necesariamente existe un triángulo con sus tres lados del mismo color. Comprueba que, si tomamos cinco puntos en lugar de seis, esto puede no ocurrir.

4. (OMG 2014/P4) Se considera un polígono regular de $90$ vértices, numerados al azar del $1$ al $90$ (cada número una sola vez). Demuestra que siempre existen dos vértices consecutivos cuyo producto de etiquetas es mayor o igual que $2014$ .

5. (OMG 2003/P4) ¿Cuál es el número máximo de vértices de un polígono regular de $21$ lados que se pueden elegir de modo que, al trazar los segmentos que los unen dos a dos, no haya dos de ellos con la misma longitud?

6. (OMG 2012/P6) Los puntos $A_1, A_2, \ldots, A_{2n}$ son los vértices de un polígono regular de $2n$ lados. Determina, en función de $n$ , el número de ternas $\{A_i, A_j, A_k\}$ tales que el triángulo $A_iA_jA_k$ es rectángulo, y el número de ternas tales que dicho triángulo es acutángulo.

7. (OMG 1999/P6) ¿Cuántas matrices de $m \times n$ casillas se pueden rellenar con ceros y unos de modo que todas las filas contengan un número par de unos? ¿En cuántas de estas matrices todas las columnas contienen también un número par de unos?

8. (OMG 2007/P2) Un poliedro convexo tiene por caras $12$ cuadrados, $8$ hexágonos regulares y $6$ octógonos regulares, de modo que en cada uno de sus vértices concurren exactamente un cuadrado, un hexágono y un octógono. ¿Cuántos segmentos que unen pares de vértices del poliedro son interiores a él, es decir, no son aristas ni están contenidos en ninguna cara?

9. (OMG 2001/P3) Nueve personas celebraron cuatro reuniones distintas, sentándose en cada una de ellas alrededor de una misma mesa circular. ¿Pudieron hacerlo de modo que dos personas cualesquiera no coincidieran como vecinas de mesa en más de una reunión? Razona la respuesta.

10. (OMG 2016/P6) ¿De cuántas formas se pueden pintar los vértices de un polígono con $n \geq 3$ lados usando tres colores, de modo que haya exactamente $m$ lados, con $2 \leq m \leq n$ , cuyos extremos sean de colores distintos?

11. (OMG 2024/P3) Dado un polígono regular de $n$ lados, se consideran todos los segmentos que unen dos vértices distintos, y para cada uno de ellos su punto medio. ¿Cuántos puntos medios diferentes se obtienen, en función de $n$ ?

12. (OMG 2015/P3) Un campeonato de baloncesto se juega por el sistema de liga a doble vuelta (cada par de equipos se enfrenta dos veces) y sin empates. El ganador de cada partido obtiene $2$ puntos y el perdedor $1$ punto. Al final del campeonato, la suma de los puntos obtenidos por todos los equipos salvo el campeón es de $2015$ puntos. ¿Cuántos partidos ganó el campeón?

13. (OMG 2009/P1) Tenemos $2009$ monedas repartidas en $10$ montones, cada uno con al menos tres monedas. Un movimiento consiste en elegir un montón, retirar una de sus monedas y dividir el resto en dos montones. ¿Es posible, repitiendo este movimiento, llegar a una situación en la que todos los montones tengan exactamente tres monedas?

14. (OMG 2010/P1) Sea $I_n$ el conjunto de los $n$ primeros números naturales impares; por ejemplo, $I_3 = \{1, 3, 5\}$ e $I_6 = \{1, 3, 5, 7, 9, 11\}$ . ¿Para qué valores de $n$ se puede descomponer $I_n$ en dos partes disjuntas de modo que coincidan las sumas de los números de cada una de ellas?

15. (OMG 2013/P3) En una sala de baile hay $15$ chicos y $15$ chicas dispuestos en dos filas paralelas formando $15$ parejas de baile, de modo que la diferencia de estatura entre el chico y la chica de cada pareja no supera los $10$ cm. Demuestra que, si colocamos a los mismos chicos y chicas en dos filas paralelas ordenados de menor a mayor estatura, también ocurrirá que la diferencia de estatura entre los miembros de las nuevas parejas así formadas no superará los $10$ cm.

16. (Local LIX OME, viernes por la mañana) Sea $n \geq 3$ un entero positivo. Los primeros $n$ enteros positivos, $1, 2, \ldots, n$ , se escriben en una pizarra. María realiza el siguiente proceso tantas veces como quiera: elige dos números de la pizarra y los reemplaza por los que resultan de sumarles a ambos un mismo entero positivo. Determina todos los enteros positivos $n$ para los que María puede conseguir, repitiendo este proceso, que todos los números de la pizarra sean iguales.

17. (Local LVI OME, viernes por la mañana) Sean $a_1, a_2, \ldots, a_{2020}$ números reales tales que la suma de $1009$ de ellos cualesquiera es positiva. Demuestra que la suma de los $2020$ números también es positiva.

18. (Local LVIII OME, viernes por la mañana) Un grupo de $12$ piratas de edades diferentes se reparte $2022$ monedas, de manera que cada pirata, salvo el más joven, tiene una moneda más que el siguiente más joven. A continuación, cada turno se procede así: se escoge un pirata que tenga al menos $11$ monedas, y este da una moneda a cada uno de los demás. Encuentra el mayor número de monedas que un pirata puede llegar a tener.

19. (Local LVIII OME, viernes por la tarde) En una fila hay $2022$ personas; cada una de ellas, o siempre miente o siempre dice la verdad. Todas afirman: «hay más mentirosos a mi izquierda que personas que digan la verdad a mi derecha». Determina cuántos mentirosos hay en la fila.

20. (OME Nacional 2014/P1) ¿Es posible disponer sobre una circunferencia los números $0, 1, 2, \ldots, 9$ de manera que la suma de tres números consecutivos cualesquiera sea, como mucho, a) $13$ , b) $14$ , c) $15$ ?

Pistas

Problema 1: ordena las edades de mayor a menor, $a_1 \geq a_2 \geq \cdots \geq a_{120}$ . Si $a_1+a_2+a_3 \leq 50$ , ¿qué cota se obtiene para $a_3$ y, por tanto, para todos los $a_i$ con $i \geq 3$ ? Usa esa cota para acotar la suma de las $120$ edades y compárala con $2002$ .
Problema 2: si solo hubiera dos longitudes distintas, fija uno de los puntos: los $6$ segmentos que parten de él tendrían solo esas dos longitudes, así que por el principio del palomar al menos $3$ de los otros $6$ puntos estarían a la misma distancia de él, es decir, sobre una circunferencia centrada en ese punto. Investiga cuántos puntos del plano pueden tener, dos a dos, solo dos distancias distintas entre ellos.
Problema 3: para los $\binom{6}{3}=20$ triángulos, fija uno de los seis puntos: de él salen $5$ segmentos coloreados con $2$ colores, así que por palomar al menos $3$ son del mismo color; analiza el triángulo formado por los otros extremos de esos $3$ segmentos. Para ver que con cinco puntos puede fallar, busca una $2$ -coloración de $K_5$ formada por dos ciclos de cinco vértices (un $C_5$ y su complementario, que también es un $C_5$ ), ninguno de los cuales contiene un triángulo.
Problema 4: considera los $46$ números $\{45, 46, \ldots, 90\}$ . El producto de cualesquiera dos de ellos (distintos) es al menos $45 \times 46 = 2070 \geq 2014$ . En un ciclo de $90$ vértices, el mayor conjunto de vértices sin dos consecutivos tiene tamaño $45$ . ¿Qué ocurre si intentas colocar esos $46$ números sin que dos queden en posiciones consecutivas?
Problema 5: para cada par de vértices elegidos, su «distancia» en el $21$ -ágono (la menor de las dos longitudes de arco que determina) toma un valor entre $1$ y $10$ . Si eliges $k$ vértices obtienes $\binom{k}{2}$ pares, cada uno con una distancia distinta, así que $\binom{k}{2} \leq 10$ . Esto acota $k$ ; después busca una configuración de $k$ vértices que alcance esa cota.
Problema 6: un triángulo inscrito en una circunferencia es rectángulo si y solo si uno de sus lados es un diámetro. En un $2n$ -ágono regular hay exactamente $n$ diámetros (pares de vértices opuestos), y para cada uno el tercer vértice puede ser cualquiera de los $2n-2$ restantes. Para los acutángulos, recuerda que un triángulo inscrito es obtusángulo o rectángulo precisamente cuando uno de los tres arcos que sus vértices determinan mide al menos media circunferencia; cuenta esos casos y resta del total $\binom{2n}{3}$ .
Problema 7: para la primera pregunta, cada fila es independiente: de las $2^n$ listas de ceros y unos de longitud $n$ , exactamente la mitad tiene un número par de unos (¿por qué?); eleva ese conteo a la potencia $m$ . Para la segunda, observa que puedes rellenar libremente la submatriz $(m-1)\times(n-1)$ formada por las primeras $m-1$ filas y las primeras $n-1$ columnas: la última casilla de cada una de esas filas y de esas columnas queda determinada por la paridad, y la casilla de la esquina inferior derecha queda determinada de dos formas que son automáticamente consistentes.
Problema 8: usa el lema del apretón de manos para hallar el número de vértices $V$ del poliedro: cada vértice tiene grado $3$ (en él concurren tres caras, una de cada tipo), y la suma de los lados de todas las caras es $12\cdot4+8\cdot6+6\cdot8$ . Con $V$ obtienes $\binom{V}{2}$ , el número total de segmentos entre vértices; resta las aristas y las diagonales de cada cara (un polígono de $n$ lados tiene $\binom{n}{2}-n$ diagonales).
Problema 9: cada reunión produce $9$ «parejas de vecinos» (es un ciclo de $9$ personas). Compara $4 \times 9 = 36$ con el número total de pares posibles, $\binom{9}{2}=36$ . ¿Qué tendría que ocurrir para que ningún par se repitiera? Esto equivale a descomponer las aristas de $K_9$ en $4$ ciclos hamiltonianos disjuntos: investiga la construcción de Walecki para $K_{2n+1}$ .
Problema 10: los $m$ lados con extremos de distinto color dividen al polígono en $m$ arcos de vértices, cada uno de un solo color, de modo que dos arcos consecutivos deben tener colores distintos. Cuenta primero de cuántas formas se eligen esos $m$ lados entre los $n$ totales, y después cuántas coloraciones propias con $3$ colores admite un ciclo de $m$ «bloques» (el polinomio cromático de un ciclo $C_m$ , que puedes obtener por recurrencia).
Problema 11: el punto medio del segmento que une los vértices $V_i$ y $V_j$ es $\frac{V_i+V_j}{2}$ . Si centras el polígono en el origen, este punto medio depende solo de $i+j \pmod{n}$ (la dirección desde el centro) y de $|i-j|$ (la distancia al centro, salvo el signo). Agrupa los $\binom{n}{2}$ segmentos según estos dos datos, distinguiendo los casos $n$ par e impar — en particular, ¿cuándo coincide un punto medio con el propio centro del polígono?
Problema 12: cada partido reparte siempre $3$ puntos en total ( $2$ al ganador, $1$ al perdedor), sin importar el resultado. Si hay $n$ equipos, se disputan $n(n-1)$ partidos (ida y vuelta), repartiendo $3n(n-1)$ puntos en total. El campeón juega $2(n-1)$ partidos: si gana $w$ de ellos, ¿cuántos puntos obtiene? Plantea $3n(n-1)=2015+(\text{puntos del campeón})$ y busca el único $n$ para el que existe un $w$ válido con $0\leq w\leq 2(n-1)$ .
Problema 13: en cada movimiento, el número total de monedas disminuye en $1$ y el número de montones aumenta en $1$ . Si tras $m$ movimientos todos los montones tuvieran exactamente $3$ monedas, plantea las dos ecuaciones correspondientes (total de monedas y número de montones) en función de $m$ , y comprueba si el sistema tiene solución entera.
Problema 14: la suma de los elementos de $I_n$ es $n^2$ . ¿Qué condición de paridad sobre $n$ es necesaria para repartir $n^2$ en dos partes iguales? Comprueba a mano los casos pequeños y, si $I_m$ se puede descomponer en dos partes de igual suma, intenta usar los cuatro nuevos elementos $\{2m+1,2m+3,2m+5,2m+7\}$ de $I_{m+4}$ para construir una descomposición de $I_{m+4}$ .
Problema 15: supón que, tras ordenar a los $15$ chicos y a las $15$ chicas por estatura, alguna pareja $(a_i,b_i)$ cumple $a_i-b_i>10$ (los demás casos son análogos). Considera los $16-i$ chicos más altos y las $i$ chicas más bajas: como $(16-i)+i=16>15$ , en la disposición original alguno de esos chicos debe estar emparejado con alguna de esas chicas (palomar), lo que daría una diferencia de altura mayor que $10$ .
Problema 16: cada movimiento suma una misma cantidad $d>0$ a dos números de la pizarra, por lo que la suma total aumenta en $2d$ , un número par: la paridad de la suma total es un invariante. Calcula la paridad de la suma inicial $1+2+\cdots+n=\frac{n(n+1)}{2}$ según el resto de $n$ módulo $4$ , y compárala con la paridad de la suma final $nv$ (donde $v$ es el valor común). ¿Para qué valores de $n$ resulta esto imposible? Para los demás, busca una construcción explícita por casos.
Problema 17: suma las $2020$ desigualdades que se obtienen al tomar, para cada $i=1,\ldots,2020$ , los $1009$ números consecutivos (de forma cíclica) $a_i, a_{i+1}, \ldots, a_{i+1008}$ . Cada $a_j$ aparece exactamente $1009$ veces en el total de esa suma. Relaciona el resultado con $1009 \cdot S$ , siendo $S$ la suma de los $2020$ números, y concluye el signo de $S$ .
Problema 18: comprueba que en cada turno el total de monedas ( $2022$ ) se conserva, y que el resto módulo $12$ de cada pirata aumenta en $1$ (ya que $-11 \equiv +1 \pmod{12}$ ). Por tanto, los $12$ restos módulo $12$ son siempre una permutación de $\{0,1,\ldots,11\}$ . Para maximizar las monedas de un pirata, los otros $11$ deben tener la menor cantidad posible siendo no negativos y con restos distintos entre sí — ¿qué valores mínimos pueden tomar?
Problema 19: numera a las personas de izquierda a derecha. Demuestra por inducción que las primeras $k$ personas son mentirosas: si la persona $k+1$ dijera la verdad, ¿cuántos mentirosos tendría a su izquierda y cuántas personas veraces, como máximo, a su derecha? Combina esto con la información del mentiroso situado más a la derecha para obtener una cota que determine el valor exacto de $k$ .
Problema 20: quita el $0$ de la circunferencia: quedan $9$ números cuya suma total es $1+2+\cdots+9=45$ . Agrúpalos en tres tríos de números consecutivos en la circunferencia. ¿Qué te dice esto sobre la suma máxima posible de un trío?