Sea [math]N\geq 2 un entero dado. Los [math]N(N+1) jugadores de un grupo de futbolistas, todos de distinta estatura, se colocan en fila. El técnico desea quitar [math]N(N-1) jugadores de esta fila, de modo que la fila resultante formada por los [math]2N jugadores restantes satisfaga las [math]N condiciones siguientes:
[math](1) Que no quede nadie ubicado entre los dos jugadores más altos.
[math](2) Que no quede nadie ubicado entre el tercer jugador más alto y el cuarto jugador más alto.
[math]\vdots
[math](N) Que no quede nadie ubicado entre los dos jugadores de menor estatura.
Sea [math]a_1,a_2,...a_{N^2+N} una sucesion de enteros positivos distintos y sea [math]b_1,b_2,...,b_{N^2+N} un reordenamiento de ellos de forma tal que [math]b_1<b_2<...<b_{N^2+N}. Queremos ver que se pueden elegir algunos de forma tal que se cumplan las condiciones del enunciado. Sea [math]B_i=\{b_x\colon{}(n+1)(i-1)+1\leq{x}\leq{}(n+1)i,x\in{\mathbb{Z}}\} para todo [math]1\leq{i}\leq{N}. Probaremos el enunciado mediante induccion en [math]N, utlizando como hipotesis inductiva que el conjunto que se arma utiliza exactamente dos de cada conjunto [math]B_i, y que estos aparecen de forma consecutiva en la sucesion que armamos.
El caso base [math]N=2 vale, pues por palomar entre los primeros [math]3 tengo que aparecen dos de alguno de [math]B_1 o [math]B_2, dejando como mucho [math]1 del otro y haciendo que entre los ultimos [math]3 haya [math]2 del otro, entonces tomo esos [math]4, y es claro que los dos de [math]B_2 son los mas grandes y los de [math]B_1 los mas chicos, y entre ellos no hay ninguno de los otros dos por construccion.
Supongamos ahora que vale para [math]N-1. Lo vamos a probar para [math]N. Tomemos los primeros [math]N+1 numeros de la sucesion de [math]a's. Por palomar existen dos pertenecientes al mismo grupito de [math]B. Tomamos aquellos dos cuyo elemento que este mas a la derecha en la sucesion de [math]a's este mas a la izquierda posible (en otras palabras, vamos recorriendo de izquierda a derecha la sucesion de [math]a's y nos agarramos la primera aparicion de dos que esten en el mismo [math]B.). Supongamos que estaban en el [math]B_j. 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]B_j. Notemos que como mucho borramos [math]2N numeros y de cada grupito [math]B borramos como mucho [math]1 (salvo de [math]B_j que lo eliminamos). Entonces nos quedaron al menos [math]N^2-N=(N-1)^2+(N-1) 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]N-1 (salvo que en algunos tengo demas). Ahora de los grupitos [math]B 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.
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.
