El enunciado de un problema para la IMO (Olimpiada Internacional de Matem\u00e1ticas) de 1984 es<\/p>\n
\n Sea c un entero positivo. La sucesi\u00f3n f(n) est\u00e1 definida por<\/p>\n
\n f(1) = 1, f(2) = c, f(n+1) = 2f(n) – f(n-1) + 2 (n \u2265 2).\n <\/p><\/blockquote>\n
Demostrar que para cada k \u2208 N exist un r \u2208 N tal que f(k)f(k+1) = f(r).\n<\/p><\/blockquote>\n
Definir la funci\u00f3n<\/p>\n
\n sucesion :: Integer -> [Integer]\n<\/pre>\ntal que los elementos de (sucesion c) son los t\u00e9rminos de la suceci\u00f3n f(n) definida en el enunciado del problema. Por ejemplo,<\/p>\n
\n take 7 (sucesion 2) == [1,2,5,10,17,26,37]\n take 7 (sucesion 3) == [1,3,7,13,21,31,43]\n take 7 (sucesion 4) == [1,4,9,16,25,36,49]\n sucesion 2 !! 30 == 901\n sucesion 3 !! 30 == 931\n sucesion 4 !! 30 == 961\n sucesion 2 !! (10^2) == 10001\n sucesion 2 !! (10^3) == 1000001\n sucesion 2 !! (10^4) == 100000001\n sucesion 2 !! (10^5) == 10000000001\n sucesion 2 !! (10^6) == 1000000000001\n sucesion 2 !! (10^7) == 100000000000001\n sucesion 3 !! (10^7) == 100000010000001\n sucesion 4 !! (10^7) == 100000020000001\n sucesion 2 !! (10^8) == 10000000000000001\n sucesion 3 !! (10^8) == 10000000100000001\n sucesion 4 !! (10^8) == 10000000200000001\n sucesion 2 !! (10^9) == 1000000000000000001\n<\/pre>\nComprobar con QuickCheck que para cada k \u2208 N existe un r \u2208 N tal que f(k)f(k+1) = f(r).<\/p>\n
Soluciones<\/h4>\n
\nimport Test.QuickCheck (Property, (==>), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsucesion :: Integer -> [Integer]\nsucesion c =\n map (termino c) [1..]\n\ntermino :: Integer -> Integer -> Integer\ntermino c 1 = 1\ntermino c 2 = c\ntermino c n = 2 * termino c (n-1) - termino c (n-2) + 2\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsucesion2 :: Integer -> [Integer]\nsucesion2 c =\n 1 : c : [2*y-x+2 | (x,y) <- zip (sucesion3 c) (tail (sucesion3 c))]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsucesion3 :: Integer -> [Integer]\nsucesion3 c =\n map (termino3 c) [1..]\n\ntermino3 :: Integer -> Integer -> Integer\ntermino3 c 1 = 1\ntermino3 c 2 = c\ntermino3 c n = n^2 + b*n - b\n where b = c - 4\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> sucesion 2 !! 32\n-- 1025\n-- (3.95 secs, 1,991,299,256 bytes)\n-- \u03bb> sucesion2 2 !! 32\n-- 1025\n-- (0.01 secs, 119,856 bytes)\n-- \u03bb> sucesion3 2 !! 32\n-- 1025\n-- (0.01 secs, 111,176 bytes)\n--\n-- \u03bb> sucesion2 2 !! (10^7)\n-- 100000000000001\n-- (2.26 secs, 5,200,111,128 bytes)\n-- \u03bb> sucesion3 2 !! (10^7)\n-- 100000000000001\n-- (0.27 secs, 1,600,111,568 bytes)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_equivalencia :: Integer -> Int -> Property\nprop_equivalencia c k =\n c > 0 && k >= 0 ==>\n take 20 (sucesion c) == take 20 (sucesion2 c) &&\n sucesion2 c !! k == sucesion3 c !! k\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_equivalencia\n-- +++ OK, passed 100 tests.\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_sucesion :: Integer -> Int -> Property\nprop_sucesion c k =\n c > 0 && k >= 0 ==>\n (ys !! k) `elem` xs\n where xs = sucesion2 c\n ys = zipWith (*) xs (tail xs)\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_sucesion\n-- +++ OK, passed 100 tests.\n<\/pre>\nEn los comentarios se pueden escribir otras soluciones, escribiendo el c\u00f3digo entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre><\/p>\n","protected":false},"excerpt":{"rendered":"
El enunciado de un problema para la IMO (Olimpiada Internacional de Matem\u00e1ticas) de 1984 es Sea c un entero positivo. La sucesi\u00f3n f(n) est\u00e1 definida por f(1) = 1, f(2) = c, f(n+1) = 2f(n) – f(n-1) + 2 (n \u2265 2). Demostrar que para cada k \u2208 N exist un r \u2208 N tal…<\/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\/6531"}],"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=6531"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6531\/revisions"}],"predecessor-version":[{"id":6540,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6531\/revisions\/6540"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6531"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6531"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}