IMO 2020 Problema 4

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 186
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 4
Nivel: 3

IMO 2020 Problema 4

Mensaje sin leer por Sandy »

Sea $n>1$ un entero. A lo largo de la pendiente de una montaña hay $n^2$ estaciones, todas a diferentes altitudes. Dos compañías de teleférico, $A$ y $B$, operan $k$ teleféricos cada una. Cada teleférico realiza el servicio desde una estación a otra de mayor altitud (sin paradas intermedias). Los teleféricos de la compañía $A$ parten de $k$ estaciones diferentes y acaban en $k$ estaciones diferentes; igualmente, si un teleférico parte de una estación más alta que la de otro, también acaba en una estación más alta que la del otro. La compañía $B$ satisface las mismas condiciones. Decimos que dos estaciones están unidas por una compañía si uno puede comenzar por la más baja y llegar a la más alta con uno o más teleféricos de esa compañía (no se permite otro tipo de movimientos entre estaciones).
Determine el menor entero positivo $k$ para el cual se puede garantizar que hay dos estaciones unidas por ambas compañías.
$u=tan\left(\frac{x}{2}\right)$
$\frac{2}{1+u^2}du=dx$

Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 186
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 4
Nivel: 3

Re: IMO 2020 Problema 4

Mensaje sin leer por Sandy »

Solución:
Spoiler: mostrar
Sea $k>n^2-n$. Tomemos los teleféricos de una sola compañía, WLOG $A$. Es claro que hay como mucho $n-1$ estaciones de las cuales no sale ningún teleférico, y como mucho $n-1$ a las cuales no entra ninguno. Luego habrá a lo sumo $n-1$ "cadenas" (donde dos estaciones pertenecen a la misma cadena si y sólo si están unidas entre sí).
Luego, al haber $n-1$ cadenas y $n^2$ estaciones, hay alguna cadena con más de $n$ estaciones. Pero lo mismo vale para la compañía $B$, luego, de las más que $n$ estaciones en la cadena más larga de $A$, no pueden estar todas en distintas cadenas de $B$, pues hay a lo sumo $n-1$ cadenas, por lo que si $k\geq n^2-n+1$ nos aseguramos que haya dos estaciones unidas por ambas compañías.

Para $k=n^2-n$, tomamos la siguiente configuración de teleféricos:
Numeramos las estaciones en orden del $1$ al $n^2$, con la $1$ abajo de todo.
La compañía $A$ tiene teleféricos que van desde la estación $i$ hasta la $i+1$ para todo $i\in \{1,2,3,...n^2-1, n^2\}$ tal que $i\not\equiv 0(n)$.
La compañía $B$ tiene teleféricos que van desde la estación $i$ hasta la estación $i+n$ para todo $i\in \{1,2,3,...n^2-n\}$.
Dos estaciones unidas por $A$ tienen siempre distancia menor que $n$, mientras que dos estaciones unidas por $B$ tienen siempre distancia mayor o igual que $n$, luego no hay dos estaciones unidas por ambas compañías. Es trivial ver que ambas compañías administran exactamente $n^2-n$ teleféricos, por lo que la solución está completa.
1  
$u=tan\left(\frac{x}{2}\right)$
$\frac{2}{1+u^2}du=dx$

Responder