{"id":6524,"date":"2021-06-17T06:00:58","date_gmt":"2021-06-17T04:00:58","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6524"},"modified":"2022-01-26T12:03:25","modified_gmt":"2022-01-26T10:03:25","slug":"maximo-valor-de-permutaciones","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/maximo-valor-de-permutaciones\/","title":{"rendered":"M\u00e1ximo valor de permutaciones"},"content":{"rendered":"<p>El enunciado de un problema para la IMO (Olimpiada Internacional de Matem\u00e1ticas) de 1982 es<\/p>\n<blockquote><p>\n  Calcular una permutaci\u00f3n (a(1),&#8230;,a(n)) de {1,2,&#8230;,n} que maximice el valor de<\/p>\n<blockquote><p>\n    a(1)a(2) + a(2)a(3) + \u00b7\u00b7\u00b7 + a(n)a(1)\n  <\/p><\/blockquote>\n<\/blockquote>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   maximoValorPermutaciones :: Integer -> Integer\n<\/pre>\n<p>tal que (maximoValorPermutaciones n) es el m\u00e1ximo valor de<\/p>\n<pre lang=\"text\">\n   a(1)a(2) + a(2)a(3) + \u00b7\u00b7\u00b7 + a(n)a(1)\n<\/pre>\n<p>para todas las permutaciones (a(1),&#8230;,a(n)) de {1,2,&#8230;,n}. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   maximoValorPermutaciones 4       ==  25\n   maximoValorPermutaciones (10^7)  ==  333333383333315000003\n   maximoValorPermutaciones (10^8)  ==  333333338333333150000003\n   maximoValorPermutaciones (10^9)  ==  333333333833333331500000003\n   length (show (maximoValorPermutaciones (10^1000)))  ==  3000\n   length (show (maximoValorPermutaciones (10^2000)))  ==  6000\n   length (show (maximoValorPermutaciones (10^3000)))  ==  9000\n<\/pre>\n<p>Comprobar con QuickCheck que, para todo entero positivo n y toda permutaci\u00f3n (a(1),&#8230;,a(n)) de {1,2,&#8230;,n},<\/p>\n<pre lang=\"text\">\n   maximoValorPermutaciones n >= a(1)a(2) + a(2)a(3) + \u00b7\u00b7\u00b7 + a(n)a(1)\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (permutations)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmaximoValorPermutaciones :: Integer -> Integer\nmaximoValorPermutaciones n =\n  maximum (map valor (permutations [1..n]))\n\nvalor :: [Integer] -> Integer\nvalor xs = sum [a * b | (a,b) <- zip xs (tail xs ++ take 1 xs)]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmaximoValorPermutaciones2 :: Integer -> Integer\nmaximoValorPermutaciones2 n =\n  valor (head (permutacionesMaximizadoras n))\n\n-- (permutacionesMaximizadoras n) es la lista de las permutaciones\n-- (a(1),...,a(n)) de {1,2,...,n} para las que el valor de\n--       a(1)a(2) + a(2)a(3) + \u00b7\u00b7\u00b7 + a(n)a(1)\n-- es m\u00e1ximo. Por ejemplo,\n--    \u03bb> permutacionesMaximizadoras 5\n--    [[3,1,2,4,5],[4,2,1,3,5],[3,5,4,2,1],[2,4,5,3,1],[2,1,3,5,4],\n--     [5,3,1,2,4],[4,5,3,1,2],[1,3,5,4,2],[5,4,2,1,3],[1,2,4,5,3]]\npermutacionesMaximizadoras :: Integer -> [[Integer]]\npermutacionesMaximizadoras n =\n  [xs | xs <- xss, valor xs == m]\n  where xss = permutations [1..n]\n        m   = maximum (map valor xss)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmaximoValorPermutaciones3 :: Integer -> Integer\nmaximoValorPermutaciones3 =\n  valor . menorPermutacionMaximizadora\n\n-- (menorPermutacionMaximizadora n) es la menor de las permutaciones\n-- (a(1),...,a(n)) de {1,2,...,n} para las que el valor de\n--       a(1)a(2) + a(2)a(3) + \u00b7\u00b7\u00b7 + a(n)a(1)\n-- es m\u00e1ximo. Por ejemplo,\n--    menorPermutacionMaximizadora 5  ==  [1,2,4,5,3]\nmenorPermutacionMaximizadora :: Integer -> [Integer]\nmenorPermutacionMaximizadora n =\n  minimum [xs | xs <- xss, valor xs == m]\n  where xss = permutations [1..n]\n        m   = maximum (map valor xss)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nmaximoValorPermutaciones4 :: Integer -> Integer\nmaximoValorPermutaciones4 =\n  valor . menorPermutacionMaximizadora2\n\n-- Redefinici\u00f3n de menorPermutacionMaximizadora observando que\n--    menorPermutacionMaximizadora 2  ==  [1,2]\n--    menorPermutacionMaximizadora 3  ==  [1,2,3]\n--    menorPermutacionMaximizadora 4  ==  [1,2,4,3]\n--    menorPermutacionMaximizadora 5  ==  [1,2,4,5,3]\n--    menorPermutacionMaximizadora 6  ==  [1,2,4,6,5,3]\n--    menorPermutacionMaximizadora 7  ==  [1,2,4,6,7,5,3]\n--    menorPermutacionMaximizadora 8  ==  [1,2,4,6,8,7,5,3]\n--    menorPermutacionMaximizadora 9  ==  [1,2,4,6,8,9,7,5,3]\nmenorPermutacionMaximizadora2 :: Integer -> [Integer]\nmenorPermutacionMaximizadora2 n\n  | even n    = 1 : [2,4..n] ++ [n-1,n-3..3]\n  | otherwise = 1 : [2,4..n] ++ [n,n-2..3]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nmaximoValorPermutaciones5 :: Integer -> Integer\nmaximoValorPermutaciones5 n\n  | even n    = valor (1 : [2,4..n] ++ [n-1,n-3..3])\n  | otherwise = valor (1 : [2,4..n] ++ [n,n-2..3])\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nmaximoValorPermutaciones6 :: Integer -> Integer\nmaximoValorPermutaciones6 1 = 1\nmaximoValorPermutaciones6 n = (2*n^3+3*n^2-11*n+18) `div` 6\n\n-- Comprobaci\u00f3n de la equivalencia\n-- ===============================\n\n-- La propiedad, para peque\u00f1os valores, es\nprop_equivalencia1 :: Integer -> Bool\nprop_equivalencia1 n =\n  and [maximoValorPermutaciones k == f k | k <- [2..n],\n                                           f <- [maximoValorPermutaciones2,\n                                                 maximoValorPermutaciones3,\n                                                 maximoValorPermutaciones4,\n                                                 maximoValorPermutaciones5,\n                                                 maximoValorPermutaciones6]]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> prop_equivalencia1 9\n--    True\n\n-- La propiedad, para grandes valores, es\nprop_equivalencia2 :: Integer -> Property\nprop_equivalencia2 n =\n  n > 0 ==>\n  maximoValorPermutaciones5 n == maximoValorPermutaciones6 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_equivalencia2\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> maximoValorPermutaciones 10\n--    368\n--    (15.33 secs, 15,147,056,648 bytes)\n--    \u03bb> maximoValorPermutaciones2 10\n--    368\n--    (15.00 secs, 15,193,414,656 bytes)\n--    \u03bb> maximoValorPermutaciones3 10\n--    368\n--    (31.86 secs, 28,297,837,624 bytes)\n--    \u03bb> maximoValorPermutaciones4 10\n--    368\n--    (0.01 secs, 104,120 bytes)\n--    \u03bb> maximoValorPermutaciones5 10\n--    368\n--    (0.01 secs, 104,264 bytes)\n--    \u03bb> maximoValorPermutaciones6 10\n--    368\n--    (0.01 secs, 102,712 bytes)\n--\n--    \u03bb> maximoValorPermutaciones4 (4*10^6)\n--    21333341333326000003\n--    (2.77 secs, 1,972,797,144 bytes)\n--    \u03bb> maximoValorPermutaciones5 (4*10^6)\n--    21333341333326000003\n--    (2.66 secs, 1,972,797,440 bytes)\n--    \u03bb> maximoValorPermutaciones6 (4*10^6)\n--    21333341333326000003\n--    (0.03 secs, 119,592 bytes)\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_maximizadora :: Integer -> Property\nprop_maximizadora n =\n  n > 0 ==>\n  do xs <- shuffle [1..n]\n     return (maximoValorPermutaciones6 n >= valor xs)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_maximizadora\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>El enunciado de un problema para la IMO (Olimpiada Internacional de Matem\u00e1ticas) de 1982 es Calcular una permutaci\u00f3n (a(1),&#8230;,a(n)) de {1,2,&#8230;,n} que maximice el valor de a(1)a(2) + a(2)a(3) + \u00b7\u00b7\u00b7 + a(n)a(1) Definir la funci\u00f3n maximoValorPermutaciones :: Integer -> Integer tal que (maximoValorPermutaciones n) es el m\u00e1ximo valor de a(1)a(2) + a(2)a(3) + \u00b7\u00b7\u00b7&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6524"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=6524"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6524\/revisions"}],"predecessor-version":[{"id":6542,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6524\/revisions\/6542"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6524"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6524"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6524"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}