El enunciado de un problema para la Olimpiada Internacional de Matem\u00e1ticas (IMO) de 1970 es<\/p>\n
\n Sean x1, x2, x3, x4, x5, x6 enteros no divisibles por 7. Demostrar que alguna de las sumas<\/p>\n
\n \u00b1x1 \u00b1 x2 \u00b1 x3 \u00b1 x4 \u00b1 x5 \u00b1 x6\n <\/p><\/blockquote>\n
es divisible por 7, donde los signos se seleccionan de todas las manera posibles. (Generalizar la propiedad para todos los primos).\n<\/p><\/blockquote>\n
Definir la funci\u00f3n<\/p>\n
\n sumas :: [Integer] -> [Integer]\n<\/pre>\ntal que (sumas xs) es la lista de los valores de las sumas<\/p>\n
\n \u00b1x(1) \u00b1 x(2) \u00b1 \u00b7\u00b7\u00b7 \u00b1 x(n)\n<\/pre>\ndonde [x(1),x(2),…,x(n)] = xs y los signos se seleccionan de todas las manera posibles. Por ejemplo,<\/p>\n
\n sort (sumas [3]) == [-3,3]\n sort (sumas [2,3]) == [-5,-1,1,5]\n sort (sumas [1,2,3]) == [-6,-4,-2,0,2,4,6]\n<\/pre>\nComprobar con QuickCheck que para todo n\u00famero primo impar p y toda lista xs de longitud (p-1) de elementos no divisibles por p se verifica que la lista (sumas xs) tiene alg\u00fan elemento divisible por p.<\/p>\n
Soluciones<\/h4>\n
\nimport Data.List (sort)\nimport Test.QuickCheck (Positive(..), Property, Gen,\n arbitrary, forAll, sample, suchThat)\nimport Data.Numbers.Primes (primes)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsumas :: [Integer] -> [Integer]\nsumas ns = map sum (expresiones ns)\n\n-- (expresiones xs) es la lista de las expresiones de la forma\n-- \u00b1x(1) \u00b1 x(2) \u00b1 \u00b7\u00b7\u00b7 \u00b1 x(n)\n-- donde [x(1),x(2),...,x(n)] = xs y los signos se seleccionan de todas\n-- las manera posibles. Por ejemplo,\n-- \u03bb> expresiones [3]\n-- [[3],[-3]]\n-- \u03bb> expresiones [2,3]\n-- [[2,3],[2,-3],[-2,3],[-2,-3]]\n-- \u03bb> expresiones [1,2,3]\n-- [[1, 2,3],[1, 2,-3],[1, -2,3],[1, -2,-3],\n-- [-1,2,3],[-1,2,-3],[-1,-2,3],[-1,-2,-3]]\nexpresiones :: [Integer] -> [[Integer]]\nexpresiones [] = [[]]\nexpresiones (n:ns) = [x:xs | x <- [n,-n], xs <- expresiones ns]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsumas2 :: [Integer] -> [Integer]\nsumas2 ns = map snd (expresiones2 ns)\n\n-- (expresiones2 xs) es la lista de las expresiones, junto con sus\n-- sumas, de la forma\n-- \u00b1x(1) \u00b1 x(2) \u00b1 \u00b7\u00b7\u00b7 \u00b1 x(n)\n-- donde [x(1),x(2),...,x(n)] = xs y los signos se seleccionan de todas\n-- las manera posibles. Por ejemplo,\n-- \u03bb> expresiones2 [3]\n-- [([3],3),([-3],-3)]\n-- \u03bb> expresiones2 [2,3]\n-- [([2,3],5),([2,-3],-1),([-2,3],1),([-2,-3],-5)]\n-- \u03bb> expresiones2 [1,2,3]\n-- [([1,2,3],6),([1,2,-3],0),([1,-2,3],2),([1,-2,-3],-4),\n-- ([-1,2,3],4),([-1,2,-3],-2),([-1,-2,3],0),([-1,-2,-3],-6)]\nexpresiones2 :: [Integer] -> [([Integer],Integer)]\nexpresiones2 [] = [([],0)]\nexpresiones2 (n:ns) = [(x:xs,x+m) | x <- [n,-n], (xs,m) <- expresiones2 ns]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_equiv :: [Integer] -> Bool\nprop_equiv xs =\n sumas ys == sumas2 ys\n where ys = take 10 xs\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_equiv\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (sumas [1..20])\n-- 1048576\n-- (2.18 secs, 3,095,500,560 bytes)\n-- \u03bb> length (sumas2 [1..20])\n-- 1048576\n-- (3.17 secs, 4,647,393,392 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_sumas :: (Positive Int) -> Property\nprop_sumas (Positive n) =\n forAll (listaNoDivisibles p (p-1)) (tieneSumaMultiplo p)\n where p = primes !! n\n\n-- (listaNoDivisibles p n) es un generador de listas de longitud n cuyos\n-- elementos son son divisibles por p. Por ejemplo,\n-- \u03bb> sample (listaNoDivisibles 5 4)\n-- [1,-1,1,-1]\n-- [2,-2,-2,-2]\n-- [3,-3,-2,2]\n-- [4,4,-4,-4]\n-- [1,8,8,1]\n-- [-4,-3,3,2]\n-- [8,-7,8,-13]\n-- [-4,-12,-13,11]\n-- [1,2,-12,-8]\n-- [-4,-16,7,7]\n-- [16,-17,16,-7]\nlistaNoDivisibles :: Integer -> Integer -> Gen [Integer]\nlistaNoDivisibles _ 0 = return []\nlistaNoDivisibles p n = do\n x <- suchThat arbitrary (\\i -> i `mod` p \/= 0)\n xs <- listaNoDivisibles p (n-1)\n return (x:xs)\n\n-- (tieneSumaMultiplo n xs) se verifica si alg\u00fan elemento de (sumas xs)\n-- es un m\u00faltiplo de n. Por ejemplo,\n-- tieneSumaMultiplo 5 [2,3] == True\n-- tieneSumaMultiplo 4 [2,3] == False\ntieneSumaMultiplo n xs =\n or [s `mod` n == 0 | s <- sumas xs]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_sumas\n-- +++ OK, passed 100 tests.\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 Olimpiada Internacional de Matem\u00e1ticas (IMO) de 1970 es Sean x1, x2, x3, x4, x5, x6 enteros no divisibles por 7. Demostrar que alguna de las sumas \u00b1x1 \u00b1 x2 \u00b1 x3 \u00b1 x4 \u00b1 x5 \u00b1 x6 es divisible por 7, donde los signos se seleccionan de todas…<\/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\/6463"}],"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=6463"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6463\/revisions"}],"predecessor-version":[{"id":6509,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6463\/revisions\/6509"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6463"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6463"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6463"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}