{"id":2467,"date":"2016-05-20T07:59:13","date_gmt":"2016-05-20T05:59:13","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2467"},"modified":"2022-03-26T14:28:51","modified_gmt":"2022-03-26T12:28:51","slug":"sucesiones-de-listas-de-numeros-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/sucesiones-de-listas-de-numeros-1\/","title":{"rendered":"Sucesiones de listas de n\u00fameros"},"content":{"rendered":"<p>En la Olimpiada Internacional de Matem\u00e1ticas del 2012 se propuso el siguiente problema:<\/p>\n<blockquote><p>\nVarios enteros positivos se escriben en una lista. Iterativamente, Alicia elige dos n\u00fameros adyacentes x e y tales que x > y y x est\u00e1 a la izquierda de y y reemplaza el par (x,y) por (y+1,x) o (x-1,x). Demostrar que s\u00f3lo puede aplicar un n\u00famero finito de dichas iteraciones.\n<\/p><\/blockquote>\n<p>Por ejemplo, las transformadas de la lista [1,3,2] son [1,2,3] y [1,3,3] y las dos obtenidas son finales (es decir, no se les puede aplicar ninguna transformaci\u00f3n).<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   soluciones       :: [Int] -> [Estado]\n   finales          :: [Int] -> [[Int]]\n   finalesMaximales :: [Int] -> (Int,[[Int]])\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(soluciones xs) es la lista de pares (n,ys) tales que ys es una lista obtenida aplic\u00e1ndole n transformaciones a xs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> soluciones [1,3,2]\n     [(1,[1,3,3]),(1,[1,2,3])]\n     \u03bb> sort (nub (soluciones [3,3,2]))\n     [(1,[3,3,3]),(2,[2,3,3]),(2,[3,3,3])]\n     \u03bb> sort (nub (soluciones [3,2,1]))\n     [(2,[2,2,3]),(3,[2,2,3]),(3,[2,3,3]),(3,[3,3,3]),(4,[2,3,3]),(4,[3,3,3])]\n<\/pre>\n<ul>\n<li>(finales xs) son las listas obtenidas transformando xs y a las que no se les puede aplicar m\u00e1s transformaciones. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     finales [1,2,3]               ==  [[1,2,3]]\n     finales [1,3,2]               ==  [[1,2,3],[1,3,3]]\n     finales [3,2,1]               ==  [[2,2,3],[2,3,3],[3,3,3]]\n     finales [1,3,2,4]             ==  [[1,2,3,4],[1,3,3,4]]\n     finales [1,3,2,3]             ==  [[1,2,3,3],[1,3,3,3]]\n     length (finales [9,6,0,7,2])  ==  19\n     length (finales [80,60..0])   ==  420\n<\/pre>\n<ul>\n<li>(finalesMaximales xs) es el par (n,yss) tal que la longitud de las cadenas m\u00e1s largas de transformaciones a partir de xs e yss es la lista de los estados finales a partir de xs con n transformaciones. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     finalesMaximales [9,5,7]   ==  (2,[[6,8,9],[8,8,9]])\n     finalesMaximales [3,2,1]   ==  (4,[[2,3,3],[3,3,3]])\n     finalesMaximales [3,2..0]  ==  (10,[[2,3,3,3],[3,3,3,3]])\n     finalesMaximales [4,3..0]  ==  (20,[[3,4,4,4,4],[4,4,4,4,4]])\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (nub, sort)\nimport I1M.BusquedaEnEspaciosDeEstados (buscaEE)\n\ntype Estado = (Int,[Int])\n\ninicial :: [Int] -> Estado\ninicial xs = (0,xs)\n\nesFinal :: Estado -> Bool\nesFinal e = null (sucesores e)\n\n--    \u03bb> sucesores [9,6,0,7,2]\n--    [[7,9,0,7,2],[8,9,0,7,2],[9,1,6,7,2],[9,5,6,7,2],[9,6,0,3,7],[9,6,0,6,7]]\nsucesores :: Estado -> [Estado]\nsucesores (_,[])  = []\nsucesores (_,[_]) = []\nsucesores (n,x:y:xs) | x > y     = [(n+1,y+1:x:xs), (n+1,x-1:x:xs)] ++ yss\n                     | otherwise = yss\n    where yss = [(m,x:ys) | (m,ys) <- sucesores (n,y:xs)]\n                       \n\nsoluciones :: [Int] -> [Estado]\nsoluciones xs =\n    buscaEE sucesores esFinal (inicial xs)\n\nfinales :: [Int] -> [[Int]]\nfinales xs =\n    sort (nub (map snd (soluciones xs)))\n            \nfinalesMaximales :: [Int] -> (Int,[[Int]])\nfinalesMaximales xs =\n    (m, [xs | (n,xs) <- es, n == m])\n    where es    = sort (nub (soluciones xs))\n          (m,_) = maximum es\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la Olimpiada Internacional de Matem\u00e1ticas del 2012 se propuso el siguiente problema: Varios enteros positivos se escriben en una lista. Iterativamente, Alicia elige dos n\u00fameros adyacentes x e y tales que x > y y x est\u00e1 a la izquierda de y y reemplaza el par (x,y) por (y+1,x) o (x-1,x). Demostrar que s\u00f3lo&#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":[7],"tags":[498,456,10,15,24,141,11,6,14],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2467"}],"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=2467"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2467\/revisions"}],"predecessor-version":[{"id":2500,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2467\/revisions\/2500"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2467"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2467"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2467"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}