{"id":1310,"date":"2019-09-07T06:52:48","date_gmt":"2019-09-07T06:52:48","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=1310"},"modified":"2019-09-07T06:52:48","modified_gmt":"2019-09-07T06:52:48","slug":"solucion-a-suma-de-productos","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2019\/09\/07\/solucion-a-suma-de-productos\/","title":{"rendered":"Soluci\u00f3n a suma de productos"},"content":{"rendered":"
Problema 2 del segundo nivel de la XXV Olimpiada de Mayo (2019)\r\nSe dirige a una edad de 14 a\u00f1os<\/pre>\n
Se tiene un tablero con 2020 casillas en la fila inferior y 2019 en la superior, de forma que est\u00e1n ubicadas las casillas de una fila entre dos de la otra, como indica la figura.<\/p>\n
En la fila inferior se colocan los n\u00fameros enteros del 1 al 2020 en alg\u00fan orden.<\/p>\n
Luego, en cada casilla superior se anota la multiplicaci\u00f3n de los dos n\u00fameros que tiene debajo.<\/p>\n
\u00bfC\u00f3mo se pueden colocar los n\u00fameros de la fila inferior para que la suma de los n\u00fameros de la fila superior sea la menor posible?
\n\"\"
\nSoluci\u00f3n:
\n
\nEne este problema se requiere un alto nivel de intuici\u00f3n y razonamiento, dif\u00edcil de encontrar a esta edad. De nuevo, vemos en la Olimpiada de Mayo una competici\u00f3n muy exigente, y es problable que este problema no obtuviese muchas puntuaciones m\u00e1ximas.<\/p>\n
De nuevo vamos a intentar ver qu\u00e9 sucede con n\u00fameros m\u00e1s bajos. Si tratamos de ordenar los n\u00fameros del 1 al 6, buscando que las sumas de los productos consecutivos sea lo menor posible, veamos qu\u00e9 sucede.<\/p>\n
1 \u2013 2 \u2013 3 \u2013 4 \u2013 5 \u2013 6 los productos son 2 + 6 + 12 + 20 + 30. Si cambiamos 5 por 1, tenemos que queda 5 \u2013 2 \u2013 3 \u2013 4 \u2013 1 \u2013 6, con lo que los productos son 10 + 6 + 12 + 4 + 6. Observamos que cambian 3 de los sumandos, no todos ellos a mejor. Sin embargo, la suma mejora. Si movemos cualquier pareja ahora, veremos que la suma aumenta.<\/p>\n
Ahora bien, esto no basta para afirmar que es la mejor distribuci\u00f3n, ya que tal vez podr\u00edamos encontrar una en la que moviendo varios a la vez, mejorara la suma de los productos. Una buena forma podr\u00eda ser encontrar alguna propiedad que cumpliese ese orden y otro no, o bien ver que si un orden creemos que es el mejor, y podemos mejorarlo, claramente no lo es.<\/p>\n
Est\u00e1 claro que hay otro orden, el inverso, en el que la suma de los productos da lo mismo (6 \u2013 1 \u2013 4 \u2013 3 \u2013 2 \u2013 5). Imagina que hay otro orden en el que tenemos la suma \u00f3ptima. Si en ese orden, el n\u00famero m\u00e1s alto no est\u00e1 en un extremo, cambiarlo con el extremo produce una suma total menor.
\nSi lo hacemos con una cadena de 8 n\u00fameros, quedan as\u00ed: 8 \u2013 1 \u2013 6 \u2013 3 \u2013 4 \u2013 5 \u2013 2 \u2013 7.<\/p>\n
Ve\u00e1moslo con \u00e1lgebra. Si el orden es x \u2013 a … y \u2013 2020 \u2013 z …, y el 2020 no est\u00e1 en un extremo, al cambiarlo al extremo (2020 \u2013 a … y \u2013 x \u2013 z …) s\u00f3lo cambia 3 valores, xa por 2020a, 2020y por xy, y 2020 por xz. Uno empeora (2020a \u2013 xa) = (2020 \u2013 x)a, mientras que hay dos que mejoran, ya que (2020 \u2013 x)y y (2020 \u2013 x)z, en total (2020 \u2013 x)(y + z). Claro, que esto depende de si la suma de y + z es menor o no que a. Probemos otra aproximaci\u00f3n.<\/p>\n
Imagina que tienes el orden  x \u2013 a … y \u2013 2020 \u2013 z …, y cambias al extremo el 2020, invirtiendo toda la cadena previa. De esta forma, todos los productos ser\u00e1n iguales menos uno, lo que nos permite compararlos. La cadena ahora ser\u00e1 2020 \u2013 y … a \u2013 x \u2013 z …, ahora la diferencia de una a otra es 2020z \u2013 zx, y como x es inferior, habremos salido ganando seguro.<\/p>\n
Por tanto, la cadena \u00f3ptima tiene el \u00faltimo valor en un extremo.<\/p>\n
Veamos que el otro extremo debe estar ocupado por el segundo n\u00famero en tama\u00f1o.<\/p>\n
De forma similar a lo anterior, si la cadena es de la forma 2020 … x \u2013 2019 \u2013 y … z, invertimos la cadena entre 2019 y el extremo, hasta que tenemos 2020 … x \u2013 z … y \u2013 2019, todos los productos son iguales excepto uno, zx sustituye a 2019x, que es claramente mayor.<\/p>\n
Ahora que est\u00e1 claro que los extremos est\u00e1n ocupados por los mayores n\u00fameros, en el problema 2020 y 2019, entre los dem\u00e1s busquemos qu\u00e9 orden nos interesa. En nuestro primer ejemplo, los menores n\u00fameros estaban junto a los mayores.<\/p>\n
Si tenemos el orden 2020 \u2013 z … x \u2013 1 \u2013 y … 2019, un orden supuestamente \u00f3ptimo donde el z no es el 1, invirtiendo de nuevo la cadena z – … – 1, tenemos 2020 \u2013 1 \u2013 x … z \u2013 y … 2019, en la que todo los productos son id\u00e9nticos, excepto dos de ellos. 2020\u00b7z es reemplazado por 2020\u00b71 y 1\u00b7y es reemplazado por z\u00b7y. En definitiva, la suma 2020\u00b7z + y es sustituida por 2020 + zy. Al restar el primer resultado menos el segundo, obtenemos 2020z \u2013 2020 + y \u2013 zy = 2020(z \u2013 1) + y(1 \u2013 z) = (z \u2013 1)(2020 \u2013 y). Como ambos n\u00fameros son mayores que 0 (2020 es mayor que y y 1 es menor que z), tenemos que esa diferencia es mayor que 0, y por eso la suma total es menor. Luego en un orden \u00f3ptimo, de nuevo 1 debe acompa\u00f1ar al 2020.<\/p>\n
De forma similar, el 2 debe ir junto al 2019, ya que en ese caso se trata del menor n\u00famero que queda. El razonamiento consiste en repetir la misma l\u00f3gica y ver que de nuevo la diferencia es positiva.<\/p>\n
Y junto al 1 y el 2, habr\u00e1 que situar de nuevo, respectivamente, al 2018 y al 2017.<\/p>\n
As\u00ed, conforme van quedando en el centro menos n\u00fameros, si los extremos son los m\u00e1s bajos, atraer\u00e1n a los m\u00e1s altos, y si son los m\u00e1s altos, atraer\u00e1n a los m\u00e1s bajos. Si repetimos el proceso, veremos que se va formando en un lado una progresi\u00f3n decreciente salteada de los pares mayores y los impares menores, y al rev\u00e9s en el otro lado. Curiosamente, al final quedan un par de sucesiones crecientes y decrecientes de pares e impares intercaladas.<\/p>\n
Para hacerlo m\u00e1s de forma m\u00e1s t\u00e9cnica, a un nivel m\u00e1s alto, deber\u00edamos probar por inducci\u00f3n que para una cadena de 2n valores diferentes, la cadena \u00f3ptima tiene esa sucesi\u00f3n en los extremos, y para hacerlo se podr\u00eda iniciar con los primeros, suponer que se cumple para los k mayores y los k menores, y ver que se cumple en el siguiente, razonando hacia el absurdo invirtiendo una cadena de valores para poder comparar s\u00f3lo un par de sumandos.<\/p>\n
En resumidas cuentas, la forma \u00f3ptima de situar los n\u00fameros ser\u00e1:<\/p>\n
2020 \u2013 1 \u2013 2018 \u2013 3 … 1014 \u2013 1009 \u2013 1012 \u2013 1011 \u2013 1010 \u2013 1013 … 4 \u2013 2017 \u2013 2 \u2013 2019.<\/p>\n","protected":false},"excerpt":{"rendered":"
Problema 2 del segundo nivel de la XXV Olimpiada de Mayo (2019) Se dirige a una edad de 14 a\u00f1os Se tiene un tablero con 2020 casillas en la fila inferior y 2019 en la superior, de forma que est\u00e1n ubicadas las casillas de una fila entre dos de la otra, como indica la figura. […]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2242018,1738,2849,3303],"tags":[],"class_list":["post-1310","post","type-post","status-publish","format-standard","hentry","category-olimpiada-de-mayo","category-olimpiadas","category-problemas","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/1310","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=1310"}],"version-history":[{"count":3,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/1310\/revisions"}],"predecessor-version":[{"id":1313,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/1310\/revisions\/1313"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=1310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=1310"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=1310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}