{"id":5289,"date":"2019-12-26T05:30:41","date_gmt":"2019-12-26T03:30:41","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5289"},"modified":"2020-01-02T09:22:13","modified_gmt":"2020-01-02T07:22:13","slug":"conjuntos-con-mas-sumas-que-restas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/conjuntos-con-mas-sumas-que-restas\/","title":{"rendered":"Conjuntos con m\u00e1s sumas que restas"},"content":{"rendered":"<p>Dado un conjunto de n\u00fameros naturales, por ejemplo A = {0, 2, 3, 4}, calculamos las sumas de todos los pares de elementos de A. Como A tiene 4 elementos hay 16 pares, pero no todas sus sumas son distintas. En este caso solo hay 8 sumas distintas: {0, 2, 3, 4, 5, 6, 7, 8}. Procediendo an\u00e1logamente hay 9 diferencias distinatas entre los pares de A: {-4, -3, -2, -1, 0, 1, 2, 3, 4}.<\/p>\n<p>Experimentando con m\u00e1s conjuntos, se puede conjeturar que el n\u00famero de restas es mayor que el de sumas y argumentar que que mientras que con dos n\u00fameros distintos s\u00f3lo se produce una suma distints sin embargo se producen dos restas distintas. Por ejemplo, con 5 y 7 s\u00f3lo se produce una suma (ya que 5+7 y 7+5 ambos dan 12) pero dos restas (ya que 5-7 y 7-5 dan -2 y 2, respectivamente).<\/p>\n<p>Sin embargo, la conjetura es falsa. Un contraejemplo en el conjunto {0, 2, 3, 4, 7, 11, 12, 14}, que tiene 26 sumas distintas con sus pares de elementos pero s\u00f3lo 25 restas.<\/p>\n<p>Los conjuntos con m\u00e1s sumas distintas con sus pares de elementos que restas se llaman conjuntos MSQR (por \u00abm\u00e1s sumas que restas\u00bb).<\/p>\n<p>El objetivo de este ejercicio es calcular los conjuntos MSQR.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   tieneMSQR :: [Integer] -> Bool\n   conjuntosMSQR :: [[Integer]]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(tieneMSQR xs) se verifica si el conjunto xs tiene m\u00e1s sumas que restas. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">  \n     tieneMSQR [0, 2, 3, 4]                 ==  False\n     tieneMSQR [0, 2, 3, 4, 7, 11, 12, 14]  ==  True\n<\/pre>\n<ul>\n<li>conjuntosMSQR es la lista de los conjuntos MSQR. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 5 conjuntosMSQR\n     [[14,12,11,7,4,3,2,0],\n      [14,12,11,10,7,3,2,0],\n      [14,13,12,9,5,4,2,1,0],\n      [14,13,12,10,9,5,2,1,0],\n      [15,13,12,8,5,4,3,1]]\n   \n      length (takeWhile (< [14]) conjuntosMSQR)   ==  0\n      length (takeWhile (< [15]) conjuntosMSQR)   ==  4\n      length (takeWhile (< [16]) conjuntosMSQR)   ==  10\n      length (takeWhile (< [17]) conjuntosMSQR)   ==  30\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (tails, nub, sort)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\n-- (sumas xs) es el conjunto de las sumas de pares de elementos de\n-- xs. Por ejemplo,\n--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]\nsumas :: [Integer] -> [Integer]\nsumas xs = nub [x + y | x <- xs, y <- xs]\n\n-- (restas xs) es el conjunto de las restas de pares de elementos de\n-- xs. Por ejemplo,\n--    restas [0,2,3,4]  ==  [0,-2,-3,-4,2,-1,3,1,4]\nrestas :: [Integer] -> [Integer]\nrestas xs = nub [x - y | x <- xs, y <- xs]\n\ntieneMSQR :: [Integer] -> Bool\ntieneMSQR xs = length (sumas xs) > length (restas xs)\n\nconjuntosMSQR :: [[Integer]]\nconjuntosMSQR = [xs | xs <- enumeracionCFN, tieneMSQR xs]\n\n-- enumeracionCFN es la enumeraci\u00f3n de los conjuntos finitos de n\u00fameros\n-- naturales del ejercicio anterior.\nenumeracionCFN :: [[Integer]]\nenumeracionCFN = concatMap enumeracionCFNHasta [0..]\n\n-- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeraci\u00f3n\n-- anterior cuyo primer elemento es n. Por ejemplo,\n--    \u03bb> enumeracionCFNHasta 1\n--    [[1],[1,0]]\n--    \u03bb> enumeracionCFNHasta 2\n--    [[2],[2,0],[2,1],[2,1,0]]\n--    \u03bb> enumeracionCFNHasta 3\n--    [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]]\nenumeracionCFNHasta :: Integer -> [[Integer]]\nenumeracionCFNHasta 0 = [[],[0]]\nenumeracionCFNHasta n =\n  [n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- (sumas2 xs) es el conjunto de las sumas de pares de elementos de\n-- xs. Por ejemplo,\n--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]\n--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]\nsumas2 :: [Integer] -> [Integer]\nsumas2 xs = nub [x + y | (x:ys) <- tails xs, y <- (x:ys)]\n\n-- (restas2 xs) es el conjunto de las restas de pares de elementos de\n-- xs. Por ejemplo,\n--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]\n--    restas2 [0,2,3,4]  ==  [0,-2,-3,-4,2,-1,3,1,4]\nrestas2 :: [Integer] -> [Integer]\nrestas2 xs = 0 : ys ++ map negate ys\n  where ys = nub [x - y | (x:ys) <- tails (sort xs), y <- ys]\n\ntieneMSQR2 :: [Integer] -> Bool\ntieneMSQR2 xs = length (sumas2 xs) > length (restas2 xs)\n\nconjuntosMSQR2 :: [[Integer]]\nconjuntosMSQR2 = [xs | xs <- enumeracionCFN, tieneMSQR2 xs]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> length (takeWhile (< [17,16..0]) conjuntosMSQR)\n--    66\n--    (21.36 secs, 10,301,222,168 bytes)\n--    \u03bb> length (takeWhile (< [17,16..0]) conjuntosMSQR2)\n--    66\n--    (10.13 secs, 7,088,969,752 bytes)\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\u00a1Qu\u00e9 f\u00e1cil es volar, qu\u00e9 f\u00e1cil es!<br \/>\nTodo consiste en no dejar que el suelo<br \/>\nse acerque a nuestros pies.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Dado un conjunto de n\u00fameros naturales, por ejemplo A = {0, 2, 3, 4}, calculamos las sumas de todos los pares de elementos de A. Como A tiene 4 elementos hay 16 pares, pero no todas sus sumas son distintas. En este caso solo hay 8 sumas distintas: {0, 2, 3, 4, 5, 6, 7,&#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":[8,58,28,415,24,11,6,14,75],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5289"}],"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=5289"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5289\/revisions"}],"predecessor-version":[{"id":5330,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5289\/revisions\/5330"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5289"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5289"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5289"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}