{"id":6402,"date":"2021-05-18T06:00:49","date_gmt":"2021-05-18T04:00:49","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6402"},"modified":"2021-05-25T08:32:42","modified_gmt":"2021-05-25T06:32:42","slug":"ternas-aditivas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/ternas-aditivas\/","title":{"rendered":"Ternas aditivas"},"content":{"rendered":"<p>El enunciado del problema C6 de la <a href=\"https:\/\/bit.ly\/3xKhMw6\">Fase Local de la Olimpiada Matem\u00e1tica Espa\u00f1ola del 2006<\/a> es<\/p>\n<blockquote><p>\n  Decimos que tres n\u00fameros naturales distintos forman una <em>terna aditiva<\/em> si la suma de los dos primeros de ellos es igual al tercero. Hallar, razonadamente, el m\u00e1ximo n\u00famero de ternas aditivas que puede haber en un conjunto dado de 20 n\u00fameros naturales.\n<\/p><\/blockquote>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   ternasAditivas  :: Integer -> [(Integer,Integer,Integer)]\n   nTernasAditivas :: Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(ternasAditivas n) es la lista de las ternas aditivas crecientes que se pueden formar con los n primeros  n\u00fameros enteros positivos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> ternasAditivas 7\n     [(1,2,3),(1,3,4),(1,4,5),(1,5,6),(1,6,7),(2,3,5),(2,4,6),(2,5,7),(3,4,7)]\n     \u03bb> length (ternasAditivas (10^4))\n     24995000\n<\/pre>\n<ul>\n<li>(nTernasAditivas n) es el n\u00famero de ternas aditivas crecientes que se pueden formar con los n primeros n\u00fameros enteros positivos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nTernasAditivas 7                            ==  9\n     length (show (nTernasAditivas (10^(10^5))))  ==  200000\n     length (show (nTernasAditivas (10^(10^6))))  ==  2000000\n     length (show (nTernasAditivas (10^(10^7))))  ==  20000000\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength)\n\n-- 1\u00aa definici\u00f3n de ternasAditivas\n-- ===============================\n\nternasAditivas :: Integer -> [(Integer,Integer,Integer)]\nternasAditivas n =\n  [(a,b,c) | a <- [1..n],\n             b <- [a+1..n],\n             let c = a+b,\n             c <= n]\n\n-- 2\u00aa definici\u00f3n de ternasAditivas\n-- ===============================\n\nternasAditivas2 :: Integer -> [(Integer,Integer,Integer)]\nternasAditivas2 n =\n  [(a,b,a+b) | a <- [1..n],\n               b <- [a+1..n-a]]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La comprobaci\u00f3n es\n--    \u03bb> and [ternasAditivas n == ternasAditivas2 n | n <- [1..300]]\n--    True\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (ternasAditivas (5*10^3))\n--    6247500\n--    (4.02 secs, 2,950,741,752 bytes)\n--    \u03bb> length (ternasAditivas2 (5*10^3))\n--    6247500\n--    (1.15 secs, 1,401,184,264 bytes)\n\n-- 1\u00aa definici\u00f3n de nTernasAditivas\n-- ================================\n\nnTernasAditivas :: Integer -> Integer\nnTernasAditivas = genericLength . ternasAditivas\n\n-- 2\u00aa definici\u00f3n de nTernasAditivas\n-- ================================\n\n-- Observando los siguientes c\u00e1lculos\n--    \u03bb> [nTernasAditivas n | n <- [1..20]]\n--    [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]\n--    \u03bb> [(n-1)^2 `div` 4 | n <- [1..20]]\n--    [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]\n\nnTernasAditivas2 :: Integer -> Integer\nnTernasAditivas2 n = (n-1)^2 `div` 4\n\n-- 3\u00aa definici\u00f3n de nTernasAditivas\n-- ================================\n\nnTernasAditivas3 :: Integer -> Integer\nnTernasAditivas3 = (`div` 4) . (^ 2) . pred\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La comprobaci\u00f3n es\n--    \u03bb> and [nTernasAditivas n == nTernasAditivas2 n | n <- [1..200]]\n--    True\n--    \u03bb> and [nTernasAditivas2 n == nTernasAditivas3 n | n <- [1..200]]\n--    True\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> nTernasAditivas (5*10^3)\n--    6247500\n--    (5.66 secs, 3,663,331,112 bytes)\n--    \u03bb> nTernasAditivas2 (5*10^3)\n--    6247500\n--    (0.02 secs, 106,752 bytes)\n--    \u03bb> nTernasAditivas3 (5*10^3)\n--    6247500\n--    (0.02 secs, 106,568 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 C6 de la Fase Local de la Olimpiada Matem\u00e1tica Espa\u00f1ola del 2006 es Decimos que tres n\u00fameros naturales distintos forman una terna aditiva si la suma de los dos primeros de ellos es igual al tercero. Hallar, razonadamente, el m\u00e1ximo n\u00famero de ternas aditivas que puede haber en un conjunto dado&#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\/6402"}],"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=6402"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6402\/revisions"}],"predecessor-version":[{"id":6485,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6402\/revisions\/6485"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6402"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6402"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6402"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}