Archivo de Enunciados • Competencias Internacionales • ICO • 2021 • Niveles Avanzado y Mayor


Problema 1
Hay $23$ rocas distribuidas alrededor de un lago circular. También hay $22$ ranas, numeradas de $1$ a $22$. Inicialmente, cada rana se coloca al azar en una roca (puede haber más de una rana en una misma roca). Cada minuto, todas las ranas saltan al mismo tiempo de la siguiente manera: la rana número $i$ salta sobre $i$ rocas en el sentido de las agujas del reloj. (En particular, la rana número $22$ salta hacia la roca vecina en el sentido contrario al de las agujas del reloj.) Demostrar que en algún momento habrá al menos $6$ rocas vacías (sin ranas).

Problema 2
Supongamos que un camión es una pieza de $1\times (k+1)$. Una playa de estacionamiento es un tablero de $(2k+1)\times (2k+1)$ y hay $t$ camiones estacionados en esta playa. Los camiones verticales solo se pueden mover en dirección vertical (en su columna) y los camiones horizontales solo se pueden mover dirección horizontal (en su fila). Un nuevo camión quiere ingresar a la playa de estacionamiento (solo puede ingresar por el borde de la playa).
1. Para $3k+1<t<4k$, demostrar que podemos mover otros camiones hacia adelante o hacia atrás de modo que el nuevo camión pueda ingresar totalmente a la playa de estacionamiento.
2. Demostrar que lo enunciado en 1. no es necesariamente cierto para $t=3k+1$.

Problema 3
Hay una hormiga en cada vértice de un cubo unitario. En el instante cero todas las hormigas comienzan a moverse lo largo de las aristas del cubo a una velocidad de una unidad por minuto. Cuando una hormiga llega a un vértice, gira alternadamente hacia la derecha y hacia la izquierda (la primera vez girará en una de estas direcciones al azar). Si dos o más hormigas se cruzan en cualquier punto del cubo, ambas mueren. Se sabe que hay una hormiga (al menos) que ha sobrevivido más de tres minutos. Demostrar que existe una
hormiga que nunca morirá.

Problema 4
El número de caminos de un grafo es el mínimo número de caminos que se necesitan para particionar los vértices del grafo. Dado un grafo conexo con número de independencia $k>1$, ¿cuál es el máximo valor posible del número de caminos de este grafo? Hallar la respuesta en términos de $k$.
El número de independencia de un grafo $G$ es el máximo posible número $k$ tal que en $G$ existen $k$ vértices no adyacentes dos a dos.

Problema 5
Definimos pieza como un conjunto de casillas conexo por aristas en la grilla infinita del plano (todas las casillas del conjunto comparten al menos una arista con otra casilla del conjunto). Hay muchas maneras de ubicar una pieza en el tablero infinito (se permiten rotaciones de $90^\circ$, pero no dar vuelta la pieza). Diremos que una pieza $T$ es especial si podemos distribuir los enteros positivos en las casillas del tablero infinito, utilizando todas las casillas, uno en cada casilla y sin repeticiones, de modo que cada número sea el máximo entre todos los números que la pieza cubre en a lo sumo una ubicación de la pieza.
1. Demostrar que cada cuadrado es una pieza especial.
2. Demostrar que cada rectángulo no cuadrado no es una pieza especial.
3. Demostrar que una pieza $T$ es especial si y solo si es exactamente la misma si se la gira $90^\circ$.

Problema 6
Sean $P$ un polígono convexo y $T$ un triángulo cuyos vértices son tres de los vértices de $P$. Si le quitamos $T$ a $P$ obtenemos $0$, $1$, $2$ o $3$ polígonos más pequeños (tal vez que comparten vértices) que llamaremos el efecto de $T$. Una triangulación de $P$ es una manera de descomponerlo en algunos triángulos utilizando diagonales que no se cortan (en el interior del polígono) Diremos que una triangulación de $P$ es linda si para cada uno de sus triángulos, el efecto de este triángulo contiene exactamente un polígono con una cantidad impar de vértices. Demostrar que una triangulación de $P$ es linda si y solo si podemos quitarle algunas de su diagonales de modo que todas las regiones de la descomposición sean cuadriláteros.

Problema 7
En un grupo de $2021$ personas, hay $1400$ que son saboteadores. El objetivo de Sherlock es descubrir al menos un saboteador. Hay varias misiones, cada una de las cuales requiere exactamente $3$ personas para ser realizada. Una misión fracasa si al menos uno de sus participantes es un saboteador. En cada ronda Sherlock elige $3$ personas, los envía a la misión y se fija si fracasa o no. ¿Cuál es el mínimo número de rondas necesarias para lograr su objetivo?