El enunciado de un problema para la IMO (Olimpiada Internacional de Matem\u00e1ticas) de 1966 es<\/p>\n
\n\n
- (a) Calcular el n\u00famero de maneras de expresar 500 como suma de n\u00fameros naturales consecutivos.<\/li>\n
- (b) Calcular el n\u00famero de tales representaciones para n = 2^x\u00b73^y\u00b75^z, con x, y, z \u2208 \u2115. \u00bfCu\u00e1ntas de ellas est\u00e1n formadas por un \u00fanico elemento?<\/li>\n
- (c) Calcular el n\u00famero de tales representaciones para un n\u00famero natural n.<\/li>\n<\/ul>\n<\/blockquote>\n
Definir las funciones<\/p>\n
\n consecutivosConSuma :: Integer -> [(Integer,Integer)]\n nDeConsecutivosConSuma :: Integer -> Integer\n<\/pre>\ntales que<\/p>\n
\n
- (consecutivosConSuma n) es la lista de los extremos de las sucesiones de n\u00fameros naturales consecutivos cuya suma es n. Por ejemplo,<\/li>\n<\/ul>\n
\n consecutivosConSuma 3 == [(0,2),(1,2),(3,3)]\n consecutivosConSuma 4 == [(4,4)]\n consecutivosConSuma 5 == [(2,3),(5,5)]\n consecutivosConSuma 6 == [(0,3),(1,3),(6,6)]\n consecutivosConSuma 15 == [(0,5),(1,5),(4,6),(7,8),(15,15)]\n maximum [length (consecutivosConSuma n) | n <- [1..1000]] == 16\n<\/pre>\n\n
- (nDeConsecutivosConSuma n) es la cantidad de sucesiones de n\u00fameros naturales consecutivos cuya suma es n. Por ejemplo,<\/li>\n<\/ul>\n
\n nDeConsecutivosConSuma 3 == 3\n nDeConsecutivosConSuma 4 == 1\n nDeConsecutivosConSuma 5 == 2\n nDeConsecutivosConSuma 6 == 3\n nDeConsecutivosConSuma 15 == 5\n maximum [nDeConsecutivosConSuma n | n <- [1..10^5]] == 49\n nDeConsecutivosConSuma (product [1..17]) == 672\n<\/pre>\nUsando las funciones anteriores, calcular las respuestas del problema de la Olimpiada.<\/p>\n
Soluciones<\/h4>\n
\nimport Data.List (genericLength, genericTake, group)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck (Positive(..), quickCheck)\n\n-- 1\u00aa definici\u00f3n de consecutivosConSuma\n-- =====================================\n\nconsecutivosConSuma :: Integer -> [(Integer,Integer)]\nconsecutivosConSuma n =\n [(x,y) | y <- [0..n],\n x <- [0..y],\n sum [x..y] == n]\n\n-- 2\u00aa definici\u00f3n de consecutivosConSuma\n-- =====================================\n\nconsecutivosConSuma2 :: Integer -> [(Integer,Integer)]\nconsecutivosConSuma2 n =\n [(x,y) | y <- [0..n],\n x <- [0..y],\n (x+y)*(y-x+1) == 2*n]\n\n-- 3\u00aa definici\u00f3n de consecutivosConSuma\n-- =====================================\n\nconsecutivosConSuma3 :: Integer -> [(Integer,Integer)]\nconsecutivosConSuma3 n\n | esTriangular n = (0, p n - 1) : [(p x, p y - 1) | (x,y) <- aux n]\n | otherwise = [(p x, p y - 1) | (x,y) <- aux n]\n where p x = posicion x triangulares\n aux n = [(x,y) | y <- zs,\n let x = y-n,\n x `elem` zs]\n where zs = genericTake (n+1) triangulares\n\n-- (esTriangular n) se verifica si n es un n\u00famero triangular (es decir,\n-- existe un m tal que n es 1+2+\u00b7\u00b7\u00b7+m). Por ejemplo,\n-- esTriangular 6 == True\n-- esTriangular 8 == False\nesTriangular :: Integer -> Bool\nesTriangular n =\n n `pertenece` triangulares\n\n-- triangulares es la sucesi\u00f3n de los n\u00fameros triangulares. Por ejemplo,\n-- take 10 triangulares == [0,1,3,6,10,15,21,28,36,45]\ntriangulares :: [Integer]\ntriangulares = scanl1 (+) [0..]\n\n-- (pertenece x ys) se verifica si x pertenece a la lista infinita\n-- creciente ys. Por ejemplo,\n-- pertenece 11 [1,3..] == True\n-- pertenece 12 [1,3..] == False\npertenece :: Ord a => a -> [a] -> Bool\npertenece x ys =\n x == head (dropWhile (< x) ys)\n\n-- (posicion x ys) es la posici\u00f3n de x en la lista ys. Por ejemplo,\n-- posicion 7 [1,3..] == 4\nposicion :: Eq a => a -> [a] -> Integer\nposicion x (y:ys) | x == y = 1\n | otherwise = 1 + posicion x ys\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> maximum [length (consecutivosConSuma2 n) | n <- [1..200]]\n-- 9\n-- (0.96 secs, 651,218,112 bytes)\n-- \u03bb> maximum [length (consecutivosConSuma3 n) | n <- [1..200]]\n-- 9\n-- (0.04 secs, 6,664,544 bytes)\n--\n-- \u03bb> maximum [length (consecutivosConSuma2 n) | n <- [1..300]]\n-- 9\n-- (3.14 secs, 2,172,860,536 bytes)\n-- \u03bb> maximum [length (consecutivosConSuma3 n) | n <- [1..300]]\n-- 9\n-- (0.16 secs, 14,523,880 bytes)\n\n-- 1\u00aa definici\u00f3n de nDeConsecutivosConSuma\n-- =======================================\n\nnDeConsecutivosConSuma :: Integer -> Integer\nnDeConsecutivosConSuma = genericLength . consecutivosConSuma\n\n-- 2\u00aa definici\u00f3n de nDeConsecutivosConSuma\n-- =======================================\n\nnDeConsecutivosConSuma2 :: Integer -> Integer\nnDeConsecutivosConSuma2 = genericLength . consecutivosConSuma2\n\n-- 3\u00aa definici\u00f3n de nDeConsecutivosConSuma\n-- =======================================\n\nnDeConsecutivosConSuma3 :: Integer -> Integer\nnDeConsecutivosConSuma3 = genericLength . consecutivosConSuma3\n\n-- C\u00e1lculo de las respuestas\n-- =========================\n\n-- El n\u00famero de maneras de expresar 500 como suma de n\u00fameros naturales\n-- consecutivos se calcula con\n-- \u03bb> nDeConsecutivosConSuma 500\n-- 4\n-- Por tanto, se puede expresar de 4 formas distintas. Dichas\n-- expresiones se pueden calcular consecutivos\n-- \u03bb> consecutivosConSuma 500\n-- [(8,32),(59,66),(98,102),(500,500)]\n-- Es decir,\n-- 500 = sum [8..32]\n-- 500 = sum [59..66]\n-- 500 = sum [98..102]\n-- 500 = sum [500..500]\n\n-- Para la segunda pregunta realizamos los siguientes c\u00e1lculos\n-- \u03bb> ts = [(x,y,z) | x <- [0..3], y <- [0..3], z <- [0..3]]\n-- \u03bb> as = [nDeConsecutivosConSuma3 (2^x*3^y*5^z) | (x,y,z) <- ts]\n-- \u03bb> as\n-- [2,2,3,4,3,5,6,8,3,7,9,12,4,8,12,16,\n-- 1,3,3,4,3,4,6,8,3,6,9,12,4,8,12,16,\n-- 1,2,3,4,2,4,7,8,4,6,9,12,4,8,12,16,\n-- 1,2,3,4,2,5,6,8,3,6,9,12,4,8,12,16]\n-- \u03bb> bs = [(y+1)*(z+1) | (x,y,z) <- ts]\n-- \u03bb> bs\n-- [1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16,\n-- 1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16,\n-- 1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16,\n-- 1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16]\n-- Casi todos elementos de as son iguales que los de bs y los que no lo\n-- son se diferencian en 1 como se observa en el siguiente c\u00e1lculo\n-- \u03bb> zipWith (-) as bs\n-- [1,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,\n-- 0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,\n-- 0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,\n-- 0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0]\n-- Los que no son iguales se calcula con\n-- \u03bb> [n | (x,y,z) <- ts, let n = 2^x*3^y*5^z, nDeConsecutivosConSuma3 n \/= (y+1)*(z+1)]\n-- [1,3,15,45,10,6,300,36,120]\n-- Dichos elementos son los n\u00fameros triangulares (es decir, los son\n-- sumas de los primeros n\u00fameros naturales) como se comprueba con\n-- \u03bb> [n | (x,y,z) <- ts, let n = 2^x*3^y*5^z, esTriangular n]\n-- [1,3,15,45,10,6,300,36,120]\n--\n-- En definitiva, el n\u00famero de representaciones de n = 2^x\u00b73^y\u00b75^z es\n-- + (y+1)*(z+1), si n no es triangular,\n-- + 1 + (y+1)*(z+1), si n es triangular,\n\n-- En el n\u00famero n = 2^x\u00b73^y\u00b75^z, la parte 3^y\u00b75^z es la parte impar de\n-- n y (y+1)*(z+1) es el n\u00famero de divisores de la parte impar de n. Por\n-- tanto, el n\u00famero de representaciones de n = 2^x\u00b73^y\u00b75^z es\n-- + el n\u00famero de divisores de la parte impar de n, si n no es triangular,\n-- + uno m\u00e1s el n\u00famero de divisores de la parte impar de n, si n es triangular,\n\n-- El c\u00e1lculo de la segunda parte del apartado (b) es\n-- \u03bb> [n | n <- [0..100], nDeConsecutivosConSuma3 n == 1]\n-- [2,4,8,16,32,64]\n-- que son las potencias de 2 con exponentes positivos.\n\n-- Finalmente, para el apartado (c), se puede generalizar el resultado\n-- anterior y el n\u00famero de representaciones de n = 2^x\u00b73^y\u00b75^z es\n-- + el n\u00famero de divisores de la parte impar de n, si n no es triangular,\n-- + uno m\u00e1s el n\u00famero de divisores de la parte impar de n, si n es triangular,\n-- donde la parte impar de n es el n\u00famero impar y tal que existe un\n-- n\u00famero natural k tal que n = 2^k\u00b7y.\n\n-- Vamas a comprobar la conjetura haciendo la siguente definici\u00f3n y\n-- comprobando que es equivalente a la anterior.\n\n-- 4\u00aa definici\u00f3n de nDeConsecutivosConSuma\n-- =======================================\n\nnDeConsecutivosConSuma4 :: Integer -> Integer\nnDeConsecutivosConSuma4 n\n | esTriangular n = 1 + (numeroDivisores (parteImpar n))\n | otherwise = numeroDivisores (parteImpar n)\n\n-- (parteImpar n) es la parte impar de n. Por ejemplo,\n-- parteImpar 60 == 15\nparteImpar :: Integer -> Integer\nparteImpar n | odd n = n\n | otherwise = parteImpar (n `div` 2)\n\n-- (numeroDivisores n) es el n\u00famero de divisores de n. Por ejemplo,\n-- numeroDivisores 12 == 6\n-- numeroDivisores 14 == 4\nnumeroDivisores :: Integer -> Integer\nnumeroDivisores =\n product . map ((+1) . genericLength) . group . primeFactors\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_equivalencia :: Positive Integer -> Bool\nprop_equivalencia (Positive n) =\n nDeConsecutivosConSuma3 n == nDeConsecutivosConSuma4 n\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_equivalencia\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> nDeConsecutivosConSuma (product [1..6])\n-- 6\n-- (2.34 secs, 8,110,570,304 bytes)\n-- \u03bb> nDeConsecutivosConSuma2 (product [1..6])\n-- 6\n-- (0.24 secs, 123,044,288 bytes)\n-- \u03bb> nDeConsecutivosConSuma3 (product [1..6])\n-- 6\n-- (0.04 secs, 443,408 bytes)\n-- \u03bb> nDeConsecutivosConSuma4 (product [1..6])\n-- 6\n-- (0.01 secs, 103,424 bytes)\n--\n-- \u03bb> nDeConsecutivosConSuma2 (product [1..7])\n-- 12\n-- (10.27 secs, 5,999,094,088 bytes)\n-- \u03bb> nDeConsecutivosConSuma3 (product [1..7])\n-- 12\n-- (0.44 secs, 2,465,936 bytes)\n-- \u03bb> nDeConsecutivosConSuma4 (product [1..7])\n-- 12\n-- (0.01 secs, 107,424 bytes)\n--\n-- \u03bb> nDeConsecutivosConSuma3 (product [1..8])\n-- 12\n-- (53.51 secs, 19,137,984 bytes)\n-- \u03bb> nDeConsecutivosConSuma4 (product [1..8])\n-- 12\n-- (0.01 secs, 107,808 bytes)\n<\/pre>\nNuevas soluciones<\/h4>\n
\n
- En los comentarios se pueden escribir nuevas soluciones.\n
- El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
El enunciado de un problema para la IMO (Olimpiada Internacional de Matem\u00e1ticas) de 1966 es (a) Calcular el n\u00famero de maneras de expresar 500 como suma de n\u00fameros naturales consecutivos. (b) Calcular el n\u00famero de tales representaciones para n = 2^x\u00b73^y\u00b75^z, con x, y, z \u2208 \u2115. \u00bfCu\u00e1ntas de ellas est\u00e1n formadas por un \u00fanico…<\/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\/6452"}],"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=6452"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6452\/revisions"}],"predecessor-version":[{"id":6507,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6452\/revisions\/6507"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6452"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6452"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6452"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}