Problema 3 de la Olimpiada Matemática Femenina Europea (EGMO 2018) Se dirige a una edad de: 16-17 años
Las n concursantes de cierta EGMO se llaman C1, C2, … ,Cn. Después de la competencia, se ponen en fila fuera del restaurante de acuerdo a las siguientes reglas:
· El Jurado escoge el orden inicial de las concursantes en la fila.
· Cada minuto, el Jurado escoge un entero i, con 1 ≤ i ≤ n.
Si la concursante Ci tiene al menos otras i concursantes delante de ella, le paga un florín al Jurado y se mueve exactamente i posiciones delante de ella.
Si la concursante Ci tiene menos de i concursantes delante de ella, el restaurante se abre y el proceso termina.
(a) Demuestre que el proceso no puede continuar indefinidamente, sin importar las elecciones del Jurado.
(b) Determine para cada n el máximo número de florines que puede recolectar el Jurado, escogiendo el orden inicial y la secuencia de movimientos astutamente.
Solución:
En este complejo problema, lo primero que debemos hacer es construir una secuencia con los movimientos más sencillos, y tratando siempre de sacar el máximo beneficio para el jurado, que es lo que nos piden.
Evidentemente, si n = 1, sólo hay una posibilidad, y el jurado no recauda nada.
Si n = 2, no conviene que estén ordenadas, así que colocan a la 1 en la segunda posición, y a la 2 en la primera. Así, pueden escoger primero el 1, que tendrá una concursante delante y por lo menos el jurado se llevará un florín. Pero después, quedarán ordenadas, con lo que sólo podrá recaudar eso.
Si miramos lo que pasa cuando juntamos 3 concursantes, ya podremos observar que si una concursante ocupa una posición menor que su número, no debe ser llamada, luego debemos sólo llamar a concursantes que estén por detrás de número, y esto ocasionará que avancen.
Tras tantear un poco las posibilidades, encontraremos la solución ideal.
Si ponemos la tercera concursante en la posición 3, será análogo al caso n = 2, pero podemos mejorar lo recaudado si colocamos en la posición 3 la 1, en la posición 2 la 2 y en la 1 la 3. Empezamos llamando a 1, que lleva a 2 a la tercera posición, volvemos luego a llamar a 1, que ordena la fila 2 – 3 – 1, después llamaremos a la 2, y eso nos dejará a 3 en la posición 3 (ya no podemos llamarla), y las jugadoras en una posición análoga al caso n = 2, 3 – 1 – 2, con lo que habremos recaudado 4 florines (2 al ordenar dos veces a las 1 y 2, y 2 para situar a la 3 en última posición.
¿Cómo podemos estar seguros?
Al parecer, el proceso tiende a ordenar la fila de mayor a menor, de forma que cada paso parece poner algo de este orden. Lo voy a situar de forma que la primera de la fila esté a la derecha, por ejemplo.
Observemos el proceso:
1 – 2 – 3 Hay 3 parejas desordenadas, 1 y 2, 1 y 3 y 2 y 3.
2 – 1 – 3 Hay 2 parejas desordenadas, 1 y 3 y 2 y 3.
2 – 3 – 1 Hay 1 pareja desordenada, 2 y 3.
3 – 1 – 2 Sigue habiendo 1 pareja desordenada, 1 y 2. Sin embargo, parece que esta pareja es “menos importante”, luego veremos por qué.
3 – 2 – 1 Todo esta en orden. Ya no podemos nombrar a ninguna sin que acabe el proceso.
Aquí parece que hay un paso crucial. En los movimientos en los que movemos al 1, siempre hay un cambio en el orden, porque 1 no puede estar en su posición ordenada, pero cuando movemos a 2, todas las concursantes invierten su posición respecto a ella, así que vuelve a producir un desorden. De esta forma, descubrimos que éste es el mayor número de movimientos posibles, aunque es difícil dar una explicación general.
Vamos a tratar de reproducir el proceso en el caso de n = 4, para tratar de aclarar la situación y encontrar una forma adecuada de describirlo.
1 – 2 – 3 – 4 Hay 6 parejas desordenadas.
2 – 1 – 3 – 4 Hay 5.
2 – 3 – 1 – 4 Hay 4.
3 – 1 – 2 – 4 Hay 4, pero cambia 2 – 3 por 1 – 2.
3 – 2 – 1 – 4 Hay 3. En este momento, hemos hecho el máximo número de movimientos sin tocar el 4.
3 – 2 – 4 – 1 Hay 2 parejas sólo.
3 – 4 – 1 – 2 Hay 2, pero cambiamos el 2 – 4 por 1 – 2.
4 – 1 – 2 – 3 Hay 3. ¡Ha subido el número de parejas desordenadas, pero cambiamos un 3 – 4 por un 1 – 2 y un 2 – 3! Indudablemente, debemos medir esto de forma que sea una ventaja.
4 – 2 – 1 – 3 Volvemos a repetir el movimiento anterior.
4 – 2 – 3 – 1 .
4 – 3 – 1 – 2 .
4 – 3 – 2 – 1 Fin. Total, 4 + 3 + 4 = 11 movimientos. Es decir, 11 florines de recaudación.
De nuevo, la clave está en que el 2 sólo puede desordenar una pareja en la que salga el 1, y el 3 puede desordenar una pareja en la que salga el 2 y el 1, y esto será en el caso más largo.
Una de las maneras de valorar esta situación es darle un peso a las parejas desordenadas, de forma que una pareja desordenada que contenga un elemento mayor sea más pesada. Por ejemplo, si la pareja tiene como elemento menor, es decir, desordenado, un número, lo valoramos como 2 elevado a ese número. Así, una pareja en la que salga el 3, tendrá un valor de 8, mientras que la pareja en la que esté desordenado el 2 valdrá 4 y la que esté el 1, valdrá 2. Y claramente, 8 es mayor que 2 + 4. Se emplean potencias de 2 porque así, cada una que tenga un número mayor “vale” el doble que la inmediatamente inferior, y cambiar una por una suma de inferiores (diferentes) es “mejor”. Observa que 8 es mayor que 4 + 2 + 1 = 7, y esto pasa para todas las potencias de 2.
Si aceptamos esta medida, cada movimiento reduce el valor del desorden al menos en 2 unidades.
Veamos, resulta que un número x que el jurado elige debe saltar x posiciones, pero sólo hay x – 1 números menores que él, de forma que como mucho puede desordenar las x – 1 parejas que forme con ellos, así que cambiará una pareja desordenada (en la que él será el menor, por lo que su valor será 2x) por x – 1 parejas en la que aparecerá él como número mayor y los valores del 1 al x – 1 como valores inferiores, y esas parejas sumarán un valor de desorden de 2 + 22 + … + 2(x – 1) = 2x – 2 (aplicando la técnica de sumar progresiones geométricas).
Se puede afinar aún más, ya que valorando cada pareja desordenada con la mitad de puntuación, cada movimiento reduce el desorden en al menos una unidad, y la suma inicial coincidiría con el número de movimientos, pero no es necesario.
Así pues, la situación más desordenada posible será el resultado de sumar el mayor desorden inicial posible, es decir, en el caso de 4 elementos 23 + 22·2 + 2·3 = 22, y dividir por 2, ya que cada paso reducimos el valor del desorden en 2 unidades como mínimo, por lo que el sistema descrito sería el mejor, y la recaudación sería exactamente ésa, 11 florines.
No sé si ha quedado claro, pero cada vez que se elige una concursante, necesariamente reduce el valor total de la fila en al menos 2. Y la forma óptima de hacerlo necesita que se den 11 pasos.
Estamos casi listos para demostrar el resultado final, y calcular el valor total de la suma máxima que puede recaudar el jurado.
Veamos que podemos alcanzar siempre a trazar un proceso en el que demos ese número de pasos.
La idea es suponer que podemos hacerlo para el valor anterior a n, como lo hemos conseguido en los pasos del 1 al 4. Es decir, que en cada paso podemos reducir el valor del desorden en 2 unidades.
Si ponemos la fila lo más desordenada posible, podemos ir deshaciendo el desorden de los n – 1 últimos sin tocar el primero, como hicimos en el 4, de forma que cada paso satisfará ese lento descenso.
Después, en un proceso de n – 1 pasos, cambiaremos la posición de los números ya ordenados por el primero y todos los anteriores. De esa forma, en cada paso, cambiaremos una pareja desordenada que tiene por valor menor x por x – 1 parejas de valores inferiores algo menores, que, como hemos visto, rebaja el valor del desorden en 2 unidades. Llegaremos al final de este proceso a que el número n está ya en su sitio, y todos los demás desordenados de nuevo, con lo que podremos volver a empezar el proceso de ordenado de los n – 1 reduciendo de 2 en 2 el desorden.
Es decir, tenemos un sistema para recaudar el máximo, el astuto sistema mediante el cual el jurado puede recaudar el máximo.
Ahora estudiemos cuál es el valor del máximo que puede recaudar. Para ello hay dos opciones. O tratar de sumar el desorden, o tratar de sacar la fórmula de forma recursiva.
Observa que el número de pasos que da el jurado en una fila n sería el doble de la fila anterior más n – 1 pasos más.por eso, empieza para n = 1 con 0, para n = 2 con 1, para n = 3, tiene 1·2 + 2 = 4, y para n = 4, 4·2 + 3 = 11. El caso n = 5 sería 11·2 + 4 = 26 lo recaudado, y para n = 6, 26·2 + 5 = 57.
Está claro que la secuencia tiene un crecimiento cercano a la exponencial de 2 (de cierta forma, la mayor parte de los movimientos multiplican por 2 la cantidad anterior).
Si los comparamos a las potencias de 2, podemos observar que 1 = 4 – 3, 4 = 8 – 4, 11 = 16 – 5, 26 = 32 – 6 y 57 = 64 – 7.
¿Será la fórmula 2n – (n + 1) válida para todos los casos? Es fácil ver que concuerda en los casos que conocemos. Ahora, si es válida para un valor determinado n – 1, eso significa que la suma de todo lo que puede recaudar es 2n – 1 – n . Si aumentamos el valor en una cantidad, esa suma sabemos que se duplicará y se le sumará n – 1, según hemos visto. Es decir, pasará a ser 2·( 2n – 1 – n ) + n – 1 = 2n – 2n + n – 1 = 2n – (n + 1), por lo que en efecto la fórmula es válida en general.
Así pues, la recaudación máxima es 2n – (n + 1), y la forma de proceder para obtenerla es situar a todas las participantes en orden ascendente, y realizar el proceso que ya se indicado en tres secuencias (ordenar todas menos la primera aplicando el método de forma recursiva, desplazar una a una la posición de la primera desordenando de paso de nuevo a todas las demás, y volver a ordenar a todas menos la última).
