Problemas de la Olimpiada
Iraní de Combinatoria
(Nivel Elemental)
2020 - 2022
Juan Neyra Faustino
Fecha de edición y traducción: Diciembre 2022
JN
I Olimpiada (2020)
1. Considere un tablero de 9×9 con un oso en la casilla central de la fila superior
y una colmena en la casilla central de la fila inferior. Queremos cavar un
agujero en 6 casillas (distintas de las casillas iniciales que contienen el oso
y la colmena) del tablero. Después de cavar los agujeros, el oso comienza a
moverse hacia la colmena. En cada paso, el oso se mueve de una casilla a
una casilla sin agujeros que tiene un borde adyacente. Los agujeros deben
elegirse de manera que haya al menos un camino válido que el oso pueda
tomar para llegar a la colmena. El oso siempre elige el camino más corto
posible. En todas las formas posibles de cavar los agujeros, ¿cuál es la máxima
cantidad de pasos que da el oso para llegar a la colmena?
2. ¿Cuál es la cantidad de sucesión de letras a, b y c de longitud 7 de manera que
no hay dos letras adyacentes iguales y no hay dos subsucesiones iguales? Una
subsucesión es un conjunto consecutivo de 2 o más letras de la secesión.
3. Considere los pares ordenados (0, 0), (0, 1), . . . , (9, 8) y (9, 9). Asigne una tar-
jeta a cada uno de estos 100 pares. Tenemos un subconjunto de estas 100
tarjetas y un dispositivo que toma dos tarjetas como (a, b) y (c, d), además de
devolver estas tarjetas, también nos da dos tarjetas más con pares ordenados
de (mı́n{a, c}, mı́n{b, d}) y (máx{a, c}, máx{b, d}). Encuentre la menor cantidad
de tarjetas necesarias para obtener las 100 tarjetas con el dispositivo.
4. La organización de la liga de fútbol de Abolfistan ha anunciado que si la pan-
demia de Corona no termina hasta diciembre, debido a la escasez de tiempo
en la próxima temporada, cada dos equipos jugarán uno contra el otro exac-
tamente una vez. Esta liga tiene 2048 equipos. Para elegir al anfitrión de cada
partido, la organización utiliza el siguiente algoritmo:
Para cada partido de la semana i, si los equipos que tienen que jugar
entre sí no han sido anfitriones la misma cantidad de partidos en las
últimas i−1 semanas, el anfitrión será el equipo que ha sido anfitrión
la menor cantidad de veces; de lo contrario, el anfitrión se elegirá
al azar.
¿Cuál es la mayor cantidad posible de veces que un equipo puede ser anfi-
trión?
5. Encuentre la cantidad total de formas posibles de dividir el conjunto {1, 2, . . . , 99}
en algunos subconjuntos de modo que el promedio de elementos en cada
subconjunto sea igual al número total de subconjuntos.
6. Para cada subconjunto no vacío S del conjunto A = {10, 12, . . . , 26}, considere
un número cS definido como
multiplicación de todos los elementos en S
cS = ,
2|S|
donde |S| es el número de elementos de S.
1
Por ejemplo, para el subconjunto S = {10, 14, 18}, tenemos cS = 10×14×18
23
. En-
cuentre X
cS .
S⊂A,S6=∅
7. Una rana está en el punto de origen del plano cartesiano. Cada vez, salta
una o dos unidades a la derecha. Sea ab la posibilidad de que la rana llegue
al punto (10, 0) después de algunos saltos, donde a y b son números enteros
positivos y mcd(a, b) = 1. Determine a + b.
8. Cada diagonal paralela a una de las diagonales principales se llama una cinta.
Por ejemplo, una cinta se muestra en la siguiente figura:
Figura 1: Una cinta.
Tenga en cuenta que cada casilla de la esquina también cuenta como una
cinta, por lo que hay 26 cintas en la figura dada. Considere un tablero de
1399 × 1399. Queremos poner algunos pines en algunas de las casillas de este
tablero de modo que cada cinta cubra un número impar de pines. Sean a y
b, respectivamente, la cantidad mínima y máxima de pines para lograr esto.
Encuentre el valor de a + b.
9. Determine la cantidad máxima de fichas que se muestran en la siguiente fi-
gura que se pueden colocar en un tablero de 10 × 10 de modo que no haya
dos que compartan un vértice.
Figura 2: Tetraminó en forma de L.
2
10. Considere el grafo que se muestra en la siguiente figura. El valor de una arista
se define como el número de aristas que lo intersecan (aparte de los extre-
mos). El valor máximo asignado a las aristas de un grafo se denomina fealdad
del grafo. Asad quiere volver a dibujar el grafo dado en la siguiente figura para
minimizar su fealdad. ¿Cuál es la fealdad mínima que puede lograr?
Figura 3: Grafo del problema 10.
11. Algunas fichas se colocan en las casillas de un tablero de 1399 × 2020. En cada
turno podemos elegir una casilla con más de una ficha, tomar dos de ellas y
colocar una de ellas en la casilla de arriba y colocar la otra en la casilla de la
derecha; Si la casilla actual es la casilla más alta de su columna, la ficha se
coloca en la casilla más baja de la columna y, de manera similar, una ficha
se mueve de la casilla más a la derecha a la casilla más a la izquierda de la
misma fila. Determine el número mínimo de fichas necesarias para que uno
pueda continuar este proceso para siempre.
12. Llamamos a un conjunto de rectángulos como un buen conjunto si se satis-
facen las siguientes propiedades:
Todos los lados de los rectángulos son horizontales o verticales.
La longitud de los lados de los rectángulos solo puede ser del conjunto
{1, 2, . . . , 10}.
La longitud de al menos un lado de cada rectángulo es 6.
La suma del área de todos los rectángulos es menor que 100.
Determine el valor mínimo de k tal que todos los rectángulos incluidos en
un conjunto bueno arbitrario puedan ubicarse en un rectángulo con ancho
10 y altura k, sin superponerse.
Lee el siguiente pasaje y responde a los siguientes 3 problemas:
Supongamos que G es un Grafo con n vértices etiquetados por 1, 2, . . . , n y A
es un subconjunto de vértices de G con número par de elementos. Queremos
elegir algunas aristas tales que el grado de cada vértice en A sea impar y el
grado de cada vértice fuera de A sea par. Denote el número mínimo de tales
aristas por f (G, A).
13. Sean n = 10 y A = {1, 2, 3, 4}. ¿Para cuántos grafos iniciales G tenemos f (G, A) =
n − 1?
3
14. Sea G un ciclo de 19 vértices. Encuentre la suma total de f (G, A) para cada
posible subconjunto A de G.
15. Sea G un grafo que se muestra en la siguiente figura.
Encuentre el número de subconjuntos A de G que satisfacen f (G, A) = 9.
4
II Olimpiada (2021)
1. ¿Cuál es la mayor cantidad de puntos que podemos colocar en un plano de
tal manera que para cualquier subconjunto de estos puntos es posible dibujar
un rectángulo cuyos lados son paralelos a los ejes de modo que todos los
puntos de este subconjunto están en el interior del rectángulo y todos los
demás puntos están fuera de él?
2. Algunos jugadores participan en un torneo de ajedrez que dura 70 días con-
secutivos. Cada día, se jugará exactamente un juego entre dos jugadores (es
posible que los juegos se repitan). El ganador de cada juego puede estar sin
jugar como máximo los siguientes 8 días y el perdedor de cada juego no ju-
gará durante al menos los siguientes 9 días. Encuentre la menor cantidad
posible de participantes de este torneo.
3. En un grupo hay 35 personas, cada una de las cuales es un mentiroso o un
caballero. Los mentirosos siempre dicen mentiras y los caballeros siempre
dicen la verdad. Para cada i, la i-ésima persona nos ha dicho que la cantidad
de caballeros en este grupo es un divisor de 2i. Halle el número de posibles
valores que puede tomar la cantidad de caballeros de este grupo.
4. Hemos llenado k casillas de un tablero de 8 × 8 con números distintos dos
a dos de tal manera que, para cada casilla llena, el número en ella es mayor
que a lo mucho uno de los números que están en sus casillas vecinas llenas.
Encuentre el mayor valor que puede tomar k.
(Dos casillas son vecinas si tienen al menos un vértice en común.)
5. Halle la cantidad de formas de cubrir completamente la figura mostrada a
continuación con fichas de dominó. Un cubrimiento completo es una forma
de colocar las fichas de dominó de modo que cada ficha cubre exactamente
dos casillas del tablero, sin superposiciones, sin dejar huecos y sin salirse del
tablero.
Figura 1: La figura que debe ser cubierta con fichas de dominó.
5
6. En cada casilla de un tablero de 10 × 10 hemos escrito uno de los números +1
o −1. Encuentre el mayor valor posible de k para el cual existen exactamente
k filas con suma positiva y exactamente k columnas con suma negativa.
7. En una competencia de combinatoria participan tres o más matemáticos. Ca-
da matemático puede hablar varios idiomas. Sabemos que cada dos matemá-
ticos pueden hablar entre ellos directamente o mediante un mediador que
es otro matemático que tiene un idioma en común con cada uno de los dos
matemáticos. Además, sabemos que si cualquier matemático abandona esta
competencia, entonces este hecho dejará de cumplirse. Halle la menor can-
tidad de idiomas distintos que hablan en conjunto todos los matemáticos.
8. Alrededor de un círculo hay 1400 personas que forman un polígono regular
de 1400 lados. Sabemos que k de ellas son honestas, que siempre dicen la
verdad, y las demás son deshonestas, que a veces dicen la verdad y a veces
mienten. Sin embargo, no sabemos quiénes son los honestos ni los desho-
nestos. Uno de ellos, el señor X, tiene un diamante en el bolsillo y quere-
mos encontrarlo. Preguntamos a cada una de las personas sobre la distancia
circular entre ella y el señor X. Encuentre el menor valor de k para el cual
podemos encontrar con total seguridad al señor X teniendo las respuestas
de todas las personas.
9. Halle la cantidad de formas de colorear las aristas de un grafo completo de
5 vértices (estos vértices están etiquetados con los números 1, 2, 3, 4, 5) con
3 colores de tal manera que cada vértice sea extremo de al menos una arista
de cada uno de los 3 colores.
(Un grafo completo es un grafo simple donde cada par de vértices está co-
nectado por una arista.)
10. Un tablero de ajedrez de 12 × 13 (12 filas y 13 columnas) está cubierto com-
pletamente con fichas de 1 × 3 de tal manera que hay exactamente k fichas
verticales en cada columna. Encuentre la cantidad de valores diferentes que
puede tomar k. Un cubrimiento completo es una forma de colocar las fichas
de 1 × 3 de modo que cada ficha cubre exactamente tres casillas del tablero,
sin superposiciones, sin dejar huecos y sin salirse del tablero.
11. Tenemos 100 vértices etiquetados del 1 al 100 alrededor de una circunfe-
rencia como se muestra en la figura. Como puedes ver, al lado de los arcos
pequeños, hay algunas aristas adicionales que conectan el vértice 49 con al-
gunos otros vértices. Encuentre la cantidad de caminos diferentes desde el
vértice 1 hasta el vértice 100 en este grafo.
6
100 1 2 3
43
54 44
53 45
52 46
51 50 47
49 48
Figura 2: Un ciclo de longitud 100, el vértice 49 está conectado
a los vértices 44-48 y 50-53.
Nota: Un camino desde el vértice u hasta el vértice w es una secuencia de
vértices distintos u = v1 , v2 , . . . , vn = w tal que vi vi+1 es una arista del grafo
para i = 1, 2, . . . , n − 1. En particular, un camino puede estar conformado por
solo un vértice.
12. En una pizarra están escritos 30 números reales (no necesariamente distin-
tos). Sabemos que no importa cómo dividamos este conjunto de números en
10 grupos de 3 números cada uno, habrá al menos 2 grupos con sumas igua-
les. Encuentre la mayor cantidad de números distintos que hay en la pizarra.
13. Halle la mayor cantidad de números de tres dígitos con dígitos del 1 al 4 que
cumplan que para cualesquiera dos de ellos, digamos a1 a2 a3 y b1 b2 b3 , existe
un índice i tal que ai + bi = 5.
14. Un punto (x, y) del plano es llamado bueno si x, y son números naturales,
x ≤ 100 y y ≤ 100. Halle la menor cantidad de rectas con pendiente + 73 que
deberíamos dibujar de tal manera que cada punto bueno pertenezca a al me-
nos una de estas rectas.
15. Halle la mayor cantidad de alfiles que podemos colocar en un tablero de
ajedrez de 8 × 8 de tal manera que cada alfil amenace como máximo a otros
tres alfiles.
(Cada alfil amenaza a otras piezas en direcciones diagonales. Si una pieza
se coloca entre dos alfiles que se amenazan, entonces esos alfiles ya no se
amenazarán entre sí).
7
III Olimpiada (2022)
1. Las casillas de un tablero de 12 × 12 han sido coloreadas de blanco y negro
como se muestra en la siguiente figura. Se nos permite intercambiar las filas
de este tablero. Encuentre la cantidad de patrones de color diferentes que
podemos obtener intercambiando estas filas varias veces.
2. Considere un grafo G que es un ciclo de longitud 2022. Un etiquetado {−1, 0, +1}
de las aristas de G se denomina “etiquetado hermoso” si para cada arista e,
la suma de las etiquetas de las aristas que comparten un extremo con e (in-
cluido e) es positiva. Para un grafo H, definimos f (H) como la menor suma
posible de un etiquetado hermoso de H. Halle f (G).
3. Hay 16 equipos en una liga de fútbol. Cada equipo juega exactamente una
vez cada semana, y los partidos de una semana son simultáneos. Cada equi-
po pertenece a una ciudad y hay exactamente un estadio de fútbol en cada
ciudad, aunque es posible que una ciudad tenga más de un equipo. Cada dos
equipos jugarán dos partidos uno contra el otro y estos partidos se llevaran a
cabo en los respectivos estadios de sus ciudades. ¿Cuál es el número mínimo
de ciudades necesarias para que pueda existir esta liga?
4. Afrouz y Morteza están jugando en un tablero de 12 × 12. Inicialmente todas
las casillas son blancas. En cada paso de este juego, Afrouz selecciona una
fila o una columna que no haya elegido antes y que no contenga una casilla
negra y la colorea completamente de rosa. Morteza cambia los colores de
una casilla blanca a negra en su turno. Afrouz inicia el juego y luego conti-
núan por turnos. Al final del juego, Morteza debe pagar a Afrouz K monedas
donde K es el número de turnos que Afrouz jugó en el juego. Si ambos juga-
dores juegan de manera óptima, ¿cuál es la cantidad de monedas que Afrouz
ganará con este juego?
5. Cada casilla de un tablero de 7 × 7 está coloreada de rojo o azul. ¿Cuál es la
mayor cantidad de L-triminós ( ) con dos casillas azules y una roja que se
pueden encontrar en el tablero?
8
6. Encuentre la cantidad de subconjuntos S entre los vértices de un polígono
regular de 11 lados tales que |S| = 4 y el cuadrilátero formado por estos 4
vértices no contiene al centro del polígono regular de 11 lados.
7. Llamamos a un número natural n especial si existe un número natural m con
las siguientes propiedades:
m > n,
la suma de los dígitos de m es igual a la suma de los dígitos de n, y
la multiplicación de los dígitos de m es igual a la multiplicación de los
dígitos de n.
¿Cuántos números especiales de siete dígitos existen?
8. ¿Cuántas ternas ordenadas (a, b, c) existen tales que a, b y c pertenecen al
conjunto {1, 3, 32, . . . , 310 } y ab × bc × ca es un cuadrado perfecto?
9. 10 niñas y 20 niños participaron en una competencia de matemáticas. Cada
participante logró un puntaje total que es un número entero no negativo.
Sabemos que el promedio de todos los puntajes es 12. Encuentre el mayor
número real r que cumple que podemos estar seguros de que existe una niña
y un niño tal que su promedio de puntajes es al menos r.
10. Para cada entero no negativo n, crearemos el nuevo número O(n) de esta
forma:
Para cada i, el i-ésimo dígito de O(n) es el dígito más a la derecha de 2ai ,
donde ai es el i-ésimo dígito de n. En el caso de que haya algunos ceros
en el lado izquierdo de O(n), todos estos ceros se eliminarán. Además, si
todos los dígitos fueran iguales a cero, entonces el valor de O(n) también es
igual a cero. Por ejemplo, O(51) = 2, O(50) = 0 y O(42) = 84. Encuentre el
número de enteros no negativos n ≤ 106 para los cuales la secuencia infinita
n, O(n), O(O(n)), . . . contiene exactamente 5 valores distintos.
11. Cada cara de un cubo de 4 × 4 × 4 se ha dividido en 16 cuadrados unitarios
de 1 × 1. Hemos cubierto la superficie de este cubo con fichas de dominó
de forma que cada ficha de dominó cubre dos cuadrados adyacentes en una
sola cara o dos cuadrados adyacentes en dos caras adyacentes. Encuentre la
máxima cantidad de fichas de dominó que cubren dos cuadrados adyacentes
de dos caras adyacentes. Tenga en cuenta que llamamos adyacentes a dos
cuadrados si ellos comparten un lado común.
12. Al principio, hay 1000 enteros distintos en la pizarra. En cada minuto, cada
uno de estos números, como x, se reemplaza por x2 o 5x. ¿Cuál es la menor
cantidad de elementos distintos en la pizarra después del final del segundo
minuto?
13. ¿Cuál es la menor cantidad de subtableros de 1 × 3 y 3 × 1 que debemos colo-
rear en un tablero de 14 × 14 para que ninguno de estos subtableros colorea-
dos comparta una casilla y después de este coloreo, cada fila y cada columna
contenga un número impar de casillas coloradas?
9
14. ¿Cuál es menor cantidad de casillas que debemos marcar en un tablero de
8 × 8, para que en cada subtablero de 1 × 4 y de 4 × 1 de este tablero, o bien
las dos casillas centrales o bien la primera y la última están marcadas? (Es
posible que se marquen 3 o incluso 4 casillas de un subtablero de 1 × 4.)
15. 100 personas están de pie alrededor de un círculo. Cada una de estas perso-
nas es un caballero o un mentiroso. Los caballeros siempre dicen la verdad.
Los mentirosos siempre mienten a los caballeros y siempre dicen la verdad a
otros mentirosos. Cada una de estas 100 personas dice una de las dos oracio-
nes “Eres un mentiroso” o “Eres un caballero” a cada una de sus dos personas
adyacentes. Si sabemos que hay 33 caballeros entre estas 100 personas y la
oración “Eres un caballero” se ha dicho exactamente 40 veces, encuentre la
cantidad de formas en que podemos elegir a dos mentirosos adyacentes.
10