Un baile con poca diferencia

Enunciado

Es un problema difícil de visualizar. Se trata de aplicar principios muy básicos, pero a veces un poco confusos. Vamos a ensayarlo con menos parejas, pongamos que tres parejas.

Supongamos que a, b y c son los chicos y A, B y C las chicas, ambos ya en orden de estaturas. Se supone que las parejas iniciales no tienen que estar en orden de estatura necesariamente, y que en ese caso, hay una diferencia entre ambos menor de 10 centímetros.

Puesto que tenemos muchas formas de emparejarlos, no podemos tratar de visualizar el problema de esa forma, ya que perderíamos mucho tiempo. Vamos a proceder por reducción al absurdo, es decir, suponer que se cumple lo contrario a lo que queremos probar, y llegar a una contradicción con lo que sabemos.

Supongamos, por tanto, que hay una pareja de las ordenadas (por ejemplo, bB), que tiene una diferencia entre ambos de 10 centímetros o más. Puede que sea más alta la chica o el chico. Supongamos que es más alto el chico (b es más alto que B), ya que el otro caso sería totalmente simétrico. ¿Qué diferencias de estatura puedo estar seguro de que se cumplen? Por el orden en que están puestos, c es aún más alto que b, por lo que no podría hacer pareja con B, y A es aún más baja que B, por lo que c tampoco podría hacer pareja con A. Así, c sólo puede hacer pareja con C, pero b no puede hacer pareja ni con B ni con A, que aún es más baja, por lo que llegamos al absurdo de que no todas las parejas iniciales podrían tener una diferencia menor de 10 centímetros.

Podemos hacer razonamientos análogos para esa diferencia en las tres parejas.

Ahora tratemos de formalizarlo para 15 parejas. Una vez que estén ordenados, podemos llamar a los chicos, por ejemplo, a₁, a₂, a₃, ..., a₁₅ y a las chicas b₁, b₂, b₃, ..., b₁₅.

Supongamos que no se cumple el resultado, que una de las parejas, a_n b_n (n es un valor entre 1 y 15, concreto) no cumple la norma y presenta una diferencia de 10 centímetros o más. Podemos suponer que a_n es más alto que b_n, aunque si fuese al revés nos limitaríamos a cambiar los nombres de los chicos por las chicas.

Ahora, tenemos n chicas más bajitas o iguales que a_n, a₁, a₂, ..., a_n, y 15 - n + 1 chicos más altos o igual que b_n (piensa que si fuese la última pareja, tendríamos uno sólo, si fuese la primera tendremos 15 chicos de esas características).

En total, tenemos a n + 15 - n + 1 = 16 personas que no podemos emparejar entre ellas, ya que la diferencia sería de 10 o más centímetros. Pero como tenemos 14 personas que sí podemos mezclar, aún podríamos hacer 14 parejas combinándolas con nuestras 16 "desemparejadas". Pero no podríamos hacer 15 en las que la diferencia fuera menor de 10 centímetros, por lo que la condición inicial no puede ser y eso es absurdo. Luego, en efecto, todas las parejas formadas por las filas en orden presentan menores diferencias.

Cambiando la altura de 10 centímetros por la menor posible, es evidente que puedes usar este método para demostrar que colocarlos en fila crea las parejas más parecidas posibles, ya que cualquier otra combinación tendrá una cota mayor que no se superará en la ordenada.