{"id":6294,"date":"2021-04-22T06:00:46","date_gmt":"2021-04-22T04:00:46","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6294"},"modified":"2021-04-29T10:48:34","modified_gmt":"2021-04-29T08:48:34","slug":"permutaciones-divisibles","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/permutaciones-divisibles\/","title":{"rendered":"Permutaciones divisibles (OME2016 P5)"},"content":{"rendered":"<p>El enunciado del <a href=\"https:\/\/bit.ly\/2Q5v1GN\">problema 5 de la OME (Olimpiada Matem\u00e1tica Espa\u00f1ola) del 2016<\/a> es<\/p>\n<blockquote><p>\n  De entre todas las permutaciones (a(1), a(2),&#8230;, a(n)) del conjunto {1, 2,&#8230;, n},(n \u2265 1 entero), se consideran las que cumplen que 2(a(1) + a(2) +\u00b7\u00b7\u00b7+ a(m)) es divisible por m, para cada m = 1, 2,&#8230;, n. Calcular el n\u00famero total de estas permutaciones.\n<\/p><\/blockquote>\n<p>Llamaremos <strong>permutaciones divisibles<\/strong> a las que cumplen la propiedad anterior. Por ejemplo, [2,3,4,1] es una permutaci\u00f3n divisible de {1,2,3,4} ya que es una permutaci\u00f3n del conjunto y se cumplen las condiciones:<\/p>\n<ul>\n<li>2*2 = 4 es divisible por 1,<\/li>\n<li>2*(2+3) = 10 es divisible por 2<\/li>\n<li>2*(2+3+4) = 18 es divisible por 3.<\/li>\n<li>2*(2+3+4+1) = 20 es divisible por 4.<\/li>\n<\/ul>\n<p>Definir las siguientes funciones:<\/p>\n<pre lang=\"text\">\n   permutacionesDivisibles  :: Integer -> [[Integer]]\n   nPermutacionesDivisibles :: Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(permutacionesDivisibles n) es la lista de las permutaciones divisibles de {1,2,&#8230;,n}. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> permutacionesDivisibles 2\n     [[1,2],[2,1]]\n     \u03bb> permutacionesDivisibles 3\n     [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]\n     \u03bb> permutacionesDivisibles 4\n     [[1,2,3,4],[1,3,2,4],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,3,1],\n      [3,1,2,4],[3,2,1,4],[3,2,4,1],[3,4,2,1],[4,2,3,1],[4,3,2,1]]\n     \u03bb> length (permutacionesDivisibles 20)\n     786432\n <\/pre>\n<ul>\n<li>(nPermutacionesDivisibles n) es el n\u00famero de permutaciones divisibles de {1,2,&#8230;,n}. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nPermutacionesDivisibles 4  ==  12\n     nPermutacionesDivisibles (10^8) `mod` (10^9)  ==  340332032\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, permutations, sort)\n\n-- 1\u00aa definici\u00f3n de permutacionesDivisibles\n-- ========================================\n\npermutacionesDivisibles :: Integer -> [[Integer]]\npermutacionesDivisibles n =\n  sort (filter aux (permutations [1..n]))\n  where\n    aux xs = and [(2*x) `mod` n == 0 | (x,n) <- zip (sumasParciales xs) [1..]]\n\n-- (sumasParciales xs) es la lista de las suas parciales de xs. Por ejemplo,\n--    sumasParciales [1..9]  ==  [1,3,6,10,15,21,28,36,45]\nsumasParciales :: [Integer] -> [Integer]\nsumasParciales = scanl1 (+)\n\n-- 2\u00aa definici\u00f3n de permutacionesDivisibles\n-- ========================================\n\npermutacionesDivisibles2 :: Integer -> [[Integer]]\npermutacionesDivisibles2 = sort . aux\n  where aux n\n          | n < 4     = permutations [1..n]\n          | otherwise = [xs ++ [n] | xs <- xss] ++\n                        [map (+1) xs ++ [1] | xs <- xss]\n          where xss = aux (n-1)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La comprobaci\u00f3n para los n primeros valores es\n--    \u03bb> and [permutacionesDivisibles2 n == permutacionesDivisibles n | n <- [1..9]]\n--    True\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (permutacionesDivisibles 10)\n--    768\n--    (8.42 secs, 10,420,281,776 bytes)\n--    \u03bb> length (permutacionesDivisibles2 10)\n--    768\n--    (0.02 secs, 2,250,152 bytes)\n--\n--    \u03bb> length (permutacionesDivisibles2 20)\n--    786432\n--    (14.33 secs, 4,458,839,736 bytes)\n\n-- 1\u00aa definici\u00f3n de nPermutacionesDivisibles\n-- =========================================\n\n--    nPermutacionesDivisibles 5  ==  24\nnPermutacionesDivisibles :: Integer -> Integer\nnPermutacionesDivisibles =\n  genericLength . permutacionesDivisibles\n\n-- 2\u00aa definici\u00f3n de nPermutacionesDivisibles\n-- =========================================\n\nnPermutacionesDivisibles2 :: Integer -> Integer\nnPermutacionesDivisibles2 =\n  genericLength . permutacionesDivisibles2\n\n-- 3\u00aa definici\u00f3n de nPermutacionesDivisibles\n-- =========================================\n\n-- Observando los siguientes c\u00e1lculos:\n--    \u03bb> [nPermutacionesDivisibles2 n | n <- [1..12]]\n--    [1,2,6,12,24,48,96,192,384,768,1536,3072]\n--    \u03bb> 1 : 2 : [3*2^(n-2) | n <- [3..12]]\n--    [1,2,6,12,24,48,96,192,384,768,1536,3072]\n\nnPermutacionesDivisibles3 :: Integer -> Integer\nnPermutacionesDivisibles3 n\n  | n < 3     = n\n  | otherwise = 3*2^(n-2)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> nPermutacionesDivisibles 10\n--    768\n--    (7.95 secs, 10,704,422,592 bytes)\n--    \u03bb> nPermutacionesDivisibles2 10\n--    768\n--    (0.01 secs, 2,269,872 bytes)\n--    \u03bb> nPermutacionesDivisibles3 10\n--    768\n--    (0.01 secs, 102,560 bytes)\n--\n--    \u03bb> nPermutacionesDivisibles2 20\n--    786432\n--    (13.00 secs, 4,477,717,968 bytes)\n--    \u03bb> nPermutacionesDivisibles3 20\n--    786432\n--    (0.01 secs, 106,848 bytes)\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 del problema 5 de la OME (Olimpiada Matem\u00e1tica Espa\u00f1ola) del 2016 es De entre todas las permutaciones (a(1), a(2),&#8230;, a(n)) del conjunto {1, 2,&#8230;, n},(n \u2265 1 entero), se consideran las que cumplen que 2(a(1) + a(2) +\u00b7\u00b7\u00b7+ a(m)) es divisible por m, para cada m = 1, 2,&#8230;, n. Calcular el n\u00famero&#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\/6294"}],"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=6294"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6294\/revisions"}],"predecessor-version":[{"id":6373,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6294\/revisions\/6373"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6294"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}