IMO 2017 - P5

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 678
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

IMO 2017 - P5

Mensaje sin leer por Gianni De Rico » Mié 19 Jul, 2017 6:47 pm

Sea [math] un entero dado. Los [math] jugadores de un grupo de futbolistas, todos de distinta estatura, se colocan en fila. El técnico desea quitar [math] jugadores de esta fila, de modo que la fila resultante formada por los [math] jugadores restantes satisfaga las [math] condiciones siguientes:

[math] Que no quede nadie ubicado entre los dos jugadores más altos.

[math] Que no quede nadie ubicado entre el tercer jugador más alto y el cuarto jugador más alto.

[math]

[math] Que no quede nadie ubicado entre los dos jugadores de menor estatura.

Demostrar que esto siempre es posible.
[math]

tuvie

Colaborador OFO - Medalla de Oro FOFO 6 años - Medalla Especial OFO - Jurado
Mensajes: 547
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 6
Nivel: Exolímpico

Re: IMO 2017 - P5

Mensaje sin leer por tuvie » Jue 20 Jul, 2017 8:16 pm

Spoiler: mostrar
Sea [math] una sucesion de enteros positivos distintos y sea [math] un reordenamiento de ellos de forma tal que [math]. Queremos ver que se pueden elegir algunos de forma tal que se cumplan las condiciones del enunciado. Sea [math] para todo [math]. Probaremos el enunciado mediante induccion en [math], utlizando como hipotesis inductiva que el conjunto que se arma utiliza exactamente dos de cada conjunto [math], y que estos aparecen de forma consecutiva en la sucesion que armamos.

El caso base [math] vale, pues por palomar entre los primeros [math] tengo que aparecen dos de alguno de [math] o [math], dejando como mucho [math] del otro y haciendo que entre los ultimos [math] haya [math] del otro, entonces tomo esos [math], y es claro que los dos de [math] son los mas grandes y los de [math] los mas chicos, y entre ellos no hay ninguno de los otros dos por construccion.

Supongamos ahora que vale para [math]. Lo vamos a probar para [math]. Tomemos los primeros [math] numeros de la sucesion de [math]. Por palomar existen dos pertenecientes al mismo grupito de [math]. Tomamos aquellos dos cuyo elemento que este mas a la derecha en la sucesion de [math] este mas a la izquierda posible (en otras palabras, vamos recorriendo de izquierda a derecha la sucesion de [math] y nos agarramos la primera aparicion de dos que esten en el mismo [math].). Supongamos que estaban en el [math]. Entonces ahora borramos de la sucesion y de los grupitos todos los que quedaron a la izquierda del que estaba mas a la derecha del que tomamos, y todos los que estaban en el grupito [math]. Notemos que como mucho borramos [math] numeros y de cada grupito [math] borramos como mucho [math] (salvo de [math] que lo eliminamos). Entonces nos quedaron al menos [math] y nos quedaron bien armados los grupitos por construccion, pues estaban ordenados bien antes, lo siguen estando ahora y es como nos hubieramos armado los grupos para [math] (salvo que en algunos tengo demas). Ahora de los grupitos [math] que no borramos nada sacamos un elemento y lo borramos de la sucesion. Entonces ahora si nos quedaron los grupitos bien armados y es el caso anterior, que por hipotesis inductiva vale, completando el paso inductivo.
Esta escrito poco formal, pero se entiende la idea.
1  

juandodyk
Mensajes: 14
Registrado: Mar 26 Jun, 2018 1:59 am
Nivel: Exolímpico

Re: IMO 2017 - P5

Mensaje sin leer por juandodyk » Mié 18 Jul, 2018 6:35 pm

Spoiler: mostrar
Tengo los $m=n(n+1)$ números $a_1,\ldots, a_{m}$ (las alturas de los jugadores). Podemos asumir que son una permutación de $\{1,\ldots,m\}$. Defino para $i=1,\ldots,n$ los conjuntos $A_i = \{ (n+1)(i-1)+1, \ldots, (n+1)i \}$, que parten a $\{1, \ldots, m\}$ en $n$ conjuntos de $n+1$ elementos.

Recorro la secuencia $a_1,\ldots,a_m$ en orden hasta que caen dos números en un mismo $A_i$ por primera vez; sean esos números $a_{k_1}$ y $a_{k_2}$, con $k_1<k_2$, y sea $i_1$ tal que $a_{k_2}\in A_{i_1}$. Elimino los números $a_1,\ldots,a_{k_2}$ y los números de $A_{i_1}$ de la secuencia. En cada $A_i$ con $i\neq i_1$ quedan al menos $n$ números, porque en $a_1,\ldots,a_{k_2}$ hay a lo sumo un número de cada $A_i$ si $i\neq i_1$. Recorro en orden los números restantes hasta que dos caen en un mismo $A_i$ por primera vez, que llamo $a_{k_3}$ y $a_{k_4}$, con $a_{k_4}\in A_{i_2}$. Elimino los números recorridos y los números de $A_{i_2}$. En cada $A_i$ con $i\neq i_2$ quedan al menos $n-1$ números (había a lo sumo uno en $a_1,\ldots,a_{k_2}$, y hay a lo sumo uno en $a_{k_2+1},\ldots,a_{k_4}$). Sigo haciendo esto. En el paso $j$ voy a tener una subsucesión $a_{k_1}, a_{k_2}, \ldots, a_{k_{2j-1}}, a_{k_{2j}}$ con $a_{k_{2r-1}}, a_{k_{2r}} \in A_{i_r}$ para $r=1,\ldots,j$, con $i_r \neq i_s$ si $r\neq s$. Y en $a_1, \ldots, a_{k_{2j}}$ van a haber aparecido a lo sumo $j$ números de $A_i$ para todo $i\not\in\{i_1,\ldots,i_j\}$. Por lo tanto en el paso siguiente voy a tener por lo menos $n+1-j$ números en cada uno de los $A_i$ restantes, que son $n-j$. Esto puede continuar mientras $n+1-j\geqq 2$ y $n-j\geqq 1$, es decir, hasta que $j=n$. Así que conseguimos una subsecuencia $a_{k_1}, \ldots, a_{k_{2n}}$ como la buscada.
¿Saben si se puede para $N(N+1)-1$? Para $N=2$ tengo un contraejemplo, pero para $N$ más grande se complica.

Responder