{"id":957,"date":"2019-01-05T08:07:00","date_gmt":"2019-01-05T08:07:00","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=957"},"modified":"2019-01-05T08:07:00","modified_gmt":"2019-01-05T08:07:00","slug":"solucion-a-una-fila-en-florencia","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2019\/01\/05\/solucion-a-una-fila-en-florencia\/","title":{"rendered":"Soluci\u00f3n a una fila en Florencia"},"content":{"rendered":"
Problema 3 de la Olimpiada Matem\u00e1tica Femenina Europea (EGMO 2018)\r\nSe dirige a una edad de: 16-17 a\u00f1os<\/pre>\n
Las n concursantes de cierta EGMO se llaman C1<\/sub>, C2<\/sub>, \u2026 ,Cn<\/sub>. Despu\u00e9s de la competencia, se ponen en fila fuera del restaurante de acuerdo a las siguientes reglas:<\/p>\n
\u00b7 El Jurado escoge el orden inicial de las concursantes en la fila.<\/p>\n
\u00b7 Cada minuto, el Jurado escoge un entero i, con 1 \u2264 i \u2264 n.<\/p>\n
Si la concursante Ci<\/sub> tiene al menos otras i concursantes delante de ella, le paga un flor\u00edn al Jurado y se mueve exactamente i posiciones delante de ella.<\/p>\n
Si la concursante Ci<\/sub> tiene menos de i concursantes delante de ella, el restaurante se abre y el proceso termina.<\/p>\n
(a) Demuestre que el proceso no puede continuar indefinidamente, sin importar las elecciones del Jurado.<\/p>\n
(b) Determine para cada n el m\u00e1ximo n\u00famero de florines que puede recolectar el Jurado, escogiendo el orden inicial y la secuencia de movimientos astutamente.\"\"
\nSoluci\u00f3n:
\nEn este complejo problema, lo primero que debemos hacer es construir una secuencia con los movimientos m\u00e1s sencillos, y tratando siempre de sacar el m\u00e1ximo beneficio para el jurado, que es lo que nos piden.<\/p>\n
Evidentemente, si n = 1, s\u00f3lo hay una posibilidad, y el jurado no recauda nada.<\/p>\n
Si n = 2, no conviene que est\u00e9n ordenadas, as\u00ed que colocan a la 1 en la segunda posici\u00f3n, y a la 2 en la primera. As\u00ed, pueden escoger primero el 1, que tendr\u00e1 una concursante delante y por lo menos el jurado se llevar\u00e1 un flor\u00edn. Pero despu\u00e9s, quedar\u00e1n ordenadas, con lo que s\u00f3lo podr\u00e1 recaudar eso.<\/p>\n
Si miramos lo que pasa cuando juntamos 3 concursantes, ya podremos observar que si una concursante ocupa una posici\u00f3n menor que su n\u00famero, no debe ser llamada, luego debemos s\u00f3lo llamar a concursantes que est\u00e9n por detr\u00e1s de n\u00famero, y esto ocasionar\u00e1 que avancen.<\/p>\n
Tras tantear un poco las posibilidades, encontraremos la soluci\u00f3n ideal.<\/p>\n
Si ponemos la tercera concursante en la posici\u00f3n 3, ser\u00e1 an\u00e1logo al caso n = 2, pero podemos mejorar lo recaudado si colocamos en la posici\u00f3n 3 la 1, en la posici\u00f3n 2 la 2 y en la 1 la 3. Empezamos llamando a 1, que lleva a 2 a la tercera posici\u00f3n, volvemos luego a llamar a 1, que ordena la fila 2 \u2013 3 \u2013 1, despu\u00e9s llamaremos a la 2, y eso nos dejar\u00e1 a 3 en la posici\u00f3n 3 (ya no podemos llamarla), y las jugadoras en una posici\u00f3n an\u00e1loga al caso n = 2, 3 \u2013 1 \u2013 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 \u00faltima posici\u00f3n.<\/p>\n
\u00bfC\u00f3mo podemos estar seguros?<\/p>\n
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\u00e9 a la derecha, por ejemplo.<\/p>\n
Observemos el proceso:<\/p>\n
1 \u2013 2 \u2013 3 Hay 3 parejas desordenadas, 1 y 2, 1 y 3 y 2 y 3.<\/p>\n
2 \u2013 1 \u2013 3 Hay 2 parejas desordenadas, 1 y 3 y 2 y 3.<\/p>\n
2 \u2013 3 \u2013 1 Hay 1 pareja desordenada, 2 y 3.<\/p>\n
3 \u2013 1 \u2013 2 Sigue habiendo 1 pareja desordenada, 1 y 2. Sin embargo, parece que esta pareja es “menos importante”, luego veremos por qu\u00e9.<\/p>\n
3 \u2013 2 \u2013 1 Todo esta en orden. Ya no podemos nombrar a ninguna sin que acabe el proceso.<\/p>\n
Aqu\u00ed 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\u00f3n ordenada, pero cuando movemos a 2, todas las concursantes invierten su posici\u00f3n respecto a ella, as\u00ed que vuelve a producir un desorden. De esta forma, descubrimos que \u00e9ste es el mayor n\u00famero de movimientos posibles, aunque es dif\u00edcil dar una explicaci\u00f3n general.<\/p>\n
Vamos a tratar de reproducir el proceso en el caso de n = 4, para tratar de aclarar la situaci\u00f3n y encontrar una forma adecuada de describirlo.<\/p>\n
1 \u2013 2 \u2013 3 \u2013 4 Hay 6 parejas desordenadas.<\/p>\n
2 \u2013 1 \u2013 3 \u2013 4 Hay 5.<\/p>\n
2 \u2013 3 \u2013 1 \u2013 4 Hay 4.<\/p>\n
3 \u2013 1 \u2013 2 \u2013 4 Hay 4, pero cambia 2 \u2013 3 por 1 \u2013 2.<\/p>\n
3 \u2013 2 \u2013 1 \u2013 4 Hay 3. En este momento, hemos hecho el m\u00e1ximo n\u00famero de movimientos sin tocar el 4.<\/p>\n
3 \u2013 2 \u2013 4 \u2013 1 Hay 2 parejas s\u00f3lo.<\/p>\n
3 \u2013 4 \u2013 1 \u2013 2 Hay 2, pero cambiamos el 2 \u2013 4 por 1 \u2013 2.<\/p>\n
4 \u2013 1 \u2013 2 \u2013 3 Hay 3. \u00a1Ha subido el n\u00famero de parejas desordenadas, pero cambiamos un 3 \u2013 4 por un 1 \u2013 2 y un 2 \u2013 3! Indudablemente, debemos medir esto de forma que sea una ventaja.<\/p>\n
4 \u2013 2 \u2013 1 \u2013 3 Volvemos a repetir el movimiento anterior.<\/p>\n
4 \u2013 2 \u2013 3 \u2013 1 .<\/p>\n
4 \u2013 3 \u2013 1 \u2013 2 .<\/p>\n
4 \u2013 3 \u2013 2 \u2013 1 Fin. Total, 4 + 3 + 4 = 11 movimientos. Es decir, 11 florines de recaudaci\u00f3n.<\/p>\n
De nuevo, la clave est\u00e1 en que el 2 s\u00f3lo 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\u00e1 en el caso m\u00e1s largo.<\/p>\n
Una de las maneras de valorar esta situaci\u00f3n es darle un peso a las parejas desordenadas, de forma que una pareja desordenada que contenga un elemento mayor sea m\u00e1s pesada. Por ejemplo, si la pareja tiene como elemento menor, es decir, desordenado, un n\u00famero, lo valoramos como 2 elevado a ese n\u00famero. As\u00ed, una pareja en la que salga el 3, tendr\u00e1 un valor de 8, mientras que la pareja en la que est\u00e9 desordenado el 2 valdr\u00e1 4 y la que est\u00e9 el 1, valdr\u00e1 2. Y claramente, 8 es mayor que 2 + 4. Se emplean potencias de 2 porque as\u00ed, cada una que tenga un n\u00famero 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.<\/p>\n
Si aceptamos esta medida, cada movimiento reduce el valor del desorden al menos en 2 unidades.<\/p>\n
Veamos, resulta que un n\u00famero x que el jurado elige debe saltar x posiciones, pero s\u00f3lo hay x \u2013 1 n\u00fameros menores que \u00e9l, de forma que como mucho puede desordenar las x \u2013 1 parejas que forme con ellos, as\u00ed que cambiar\u00e1 una pareja desordenada (en la que \u00e9l ser\u00e1 el menor, por lo que su valor ser\u00e1 2x<\/sup>) por x \u2013 1 parejas en la que aparecer\u00e1 \u00e9l como n\u00famero mayor y los valores del 1 al x \u2013 1 como valores inferiores, y esas parejas sumar\u00e1n un valor de desorden de 2 + 22<\/sup> + … + 2(x \u2013 1)<\/sup> = 2x<\/sup> \u2013 2 (aplicando la t\u00e9cnica de sumar progresiones geom\u00e9tricas).<\/p>\n
Se puede afinar a\u00fan m\u00e1s, ya que valorando cada pareja desordenada con la mitad de puntuaci\u00f3n, cada movimiento reduce el desorden en al menos una unidad, y la suma inicial coincidir\u00eda con el n\u00famero de movimientos, pero no es necesario.<\/p>\n
As\u00ed pues, la situaci\u00f3n m\u00e1s desordenada posible ser\u00e1 el resultado de sumar el mayor desorden inicial posible, es decir, en el caso de 4 elementos 23<\/sup> + 22<\/sup>\u00b72 + 2\u00b73 = 22, y dividir por 2, ya que cada paso reducimos el valor del desorden en 2 unidades como m\u00ednimo, por lo que el sistema descrito ser\u00eda el mejor, y la recaudaci\u00f3n ser\u00eda exactamente \u00e9sa, 11 florines.<\/p>\n
No s\u00e9 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 \u00f3ptima de hacerlo necesita que se den 11 pasos.<\/p>\n
Estamos casi listos para demostrar el resultado final, y calcular el valor total de la suma m\u00e1xima que puede recaudar el jurado.<\/p>\n
Veamos que podemos alcanzar siempre a trazar un proceso en el que demos ese n\u00famero de pasos.<\/p>\n
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.<\/p>\n
Si ponemos la fila lo m\u00e1s desordenada posible, podemos ir deshaciendo el desorden de los n – 1 \u00faltimos sin tocar el  primero, como hicimos en el 4, de forma que cada paso satisfar\u00e1 ese lento descenso.<\/p>\n
Despu\u00e9s, en un proceso de n \u2013 1 pasos, cambiaremos la posici\u00f3n de los n\u00fameros 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 \u2013 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\u00famero n est\u00e1 ya en su sitio, y todos los dem\u00e1s desordenados de nuevo, con lo que podremos volver a empezar el proceso de ordenado de los n \u2013 1 reduciendo de 2 en 2 el desorden.<\/p>\n
Es decir, tenemos un sistema para recaudar el m\u00e1ximo, el astuto sistema mediante el cual el jurado puede recaudar el m\u00e1ximo.<\/p>\n
Ahora estudiemos cu\u00e1l es el valor del m\u00e1ximo que puede recaudar. Para ello hay dos opciones. O tratar de sumar el desorden, o tratar de sacar la f\u00f3rmula de forma recursiva.<\/p>\n
Observa que el n\u00famero de pasos que da el jurado en una fila n ser\u00eda el doble de la fila anterior m\u00e1s n \u2013 1 pasos m\u00e1s.por eso, empieza para n = 1 con 0, para n = 2 con 1, para n = 3, tiene 1\u00b72 + 2 = 4, y para n = 4, 4\u00b72 + 3 = 11. El caso n = 5 ser\u00eda 11\u00b72 + 4 = 26 lo recaudado, y para n = 6, 26\u00b72 + 5 = 57.<\/p>\n
Est\u00e1 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).<\/p>\n
Si los comparamos a las potencias de 2, podemos observar que 1 = 4 \u2013 3, 4 = 8 \u2013 4, 11 = 16 \u2013 5, 26 = 32 \u2013 6 y 57 = 64 \u2013 7.<\/p>\n
\u00bfSer\u00e1 la f\u00f3rmula 2n<\/sup> \u2013 (n + 1) v\u00e1lida para todos los casos? Es f\u00e1cil ver que concuerda en los casos que conocemos. Ahora, si es v\u00e1lida para un valor determinado n \u2013 1, eso significa que la suma de todo lo que puede recaudar es 2n \u2013 1<\/sup> \u2013 n . Si aumentamos el valor en una cantidad, esa suma sabemos que se duplicar\u00e1 y se le sumar\u00e1 n \u2013 1, seg\u00fan hemos visto. Es decir, pasar\u00e1 a ser 2\u00b7( 2n \u2013 1<\/sup> \u2013 n ) + n \u2013 1 = 2n<\/sup> \u2013 2n + n \u2013 1 = 2n<\/sup> \u2013 (n + 1), por lo que en efecto la f\u00f3rmula es v\u00e1lida en general.<\/p>\n
As\u00ed pues, la recaudaci\u00f3n m\u00e1xima es 2n<\/sup> \u2013 (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\u00e9todo de forma recursiva, desplazar una a una la posici\u00f3n de la primera desordenando de paso de nuevo a todas las dem\u00e1s, y volver a ordenar a todas menos la \u00faltima).<\/p>\n","protected":false},"excerpt":{"rendered":"
Problema 3 de la Olimpiada Matem\u00e1tica Femenina Europea (EGMO 2018) Se dirige a una edad de: 16-17 a\u00f1os Las n concursantes de cierta EGMO se llaman C1, C2, \u2026 ,Cn. Despu\u00e9s de la competencia, se ponen en fila fuera del restaurante de acuerdo a las siguientes reglas: \u00b7 El Jurado escoge el orden inicial de […]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2242015,1738,2849,3303],"tags":[],"class_list":["post-957","post","type-post","status-publish","format-standard","hentry","category-egmo","category-olimpiadas","category-problemas","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/957","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/users\/4267"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/comments?post=957"}],"version-history":[{"count":2,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/957\/revisions"}],"predecessor-version":[{"id":959,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/957\/revisions\/959"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=957"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=957"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=957"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}