Sumas con signos
El enunciado de un problema para la Olimpiada Internacional de Matemáticas (IMO) de 1970 es
Sean x1, x2, x3, x4, x5, x6 enteros no divisibles por 7. Demostrar que alguna de las sumas
±x1 ± x2 ± x3 ± x4 ± x5 ± x6
es divisible por 7, donde los signos se seleccionan de todas las manera posibles. (Generalizar la propiedad para todos los primos).
Definir la función
|
1 |
sumas :: [Integer] -> [Integer] |
tal que (sumas xs) es la lista de los valores de las sumas
|
1 |
±x(1) ± x(2) ± ··· ± x(n) |
donde [x(1),x(2),…,x(n)] = xs y los signos se seleccionan de todas las manera posibles. Por ejemplo,
|
1 2 3 |
sort (sumas [3]) == [-3,3] sort (sumas [2,3]) == [-5,-1,1,5] sort (sumas [1,2,3]) == [-6,-4,-2,0,2,4,6] |
Comprobar con QuickCheck que para todo número 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ún elemento divisible por p.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
import Data.List (sort) import Test.QuickCheck (Positive(..), Property, Gen, arbitrary, forAll, sample, suchThat) import Data.Numbers.Primes (primes) -- 1ª solución -- =========== sumas :: [Integer] -> [Integer] sumas ns = map sum (expresiones ns) -- (expresiones xs) es la lista de las expresiones de la forma -- ±x(1) ± x(2) ± ··· ± x(n) -- donde [x(1),x(2),...,x(n)] = xs y los signos se seleccionan de todas -- las manera posibles. Por ejemplo, -- λ> expresiones [3] -- [[3],[-3]] -- λ> expresiones [2,3] -- [[2,3],[2,-3],[-2,3],[-2,-3]] -- λ> expresiones [1,2,3] -- [[1, 2,3],[1, 2,-3],[1, -2,3],[1, -2,-3], -- [-1,2,3],[-1,2,-3],[-1,-2,3],[-1,-2,-3]] expresiones :: [Integer] -> [[Integer]] expresiones [] = [[]] expresiones (n:ns) = [x:xs | x <- [n,-n], xs <- expresiones ns] -- 2ª solución -- =========== sumas2 :: [Integer] -> [Integer] sumas2 ns = map snd (expresiones2 ns) -- (expresiones2 xs) es la lista de las expresiones, junto con sus -- sumas, de la forma -- ±x(1) ± x(2) ± ··· ± x(n) -- donde [x(1),x(2),...,x(n)] = xs y los signos se seleccionan de todas -- las manera posibles. Por ejemplo, -- λ> expresiones2 [3] -- [([3],3),([-3],-3)] -- λ> expresiones2 [2,3] -- [([2,3],5),([2,-3],-1),([-2,3],1),([-2,-3],-5)] -- λ> expresiones2 [1,2,3] -- [([1,2,3],6),([1,2,-3],0),([1,-2,3],2),([1,-2,-3],-4), -- ([-1,2,3],4),([-1,2,-3],-2),([-1,-2,3],0),([-1,-2,-3],-6)] expresiones2 :: [Integer] -> [([Integer],Integer)] expresiones2 [] = [([],0)] expresiones2 (n:ns) = [(x:xs,x+m) | x <- [n,-n], (xs,m) <- expresiones2 ns] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_equiv :: [Integer] -> Bool prop_equiv xs = sumas ys == sumas2 ys where ys = take 10 xs -- La comprobación es -- λ> quickCheck prop_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (sumas [1..20]) -- 1048576 -- (2.18 secs, 3,095,500,560 bytes) -- λ> length (sumas2 [1..20]) -- 1048576 -- (3.17 secs, 4,647,393,392 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_sumas :: (Positive Int) -> Property prop_sumas (Positive n) = forAll (listaNoDivisibles p (p-1)) (tieneSumaMultiplo p) where p = primes !! n -- (listaNoDivisibles p n) es un generador de listas de longitud n cuyos -- elementos son son divisibles por p. Por ejemplo, -- λ> sample (listaNoDivisibles 5 4) -- [1,-1,1,-1] -- [2,-2,-2,-2] -- [3,-3,-2,2] -- [4,4,-4,-4] -- [1,8,8,1] -- [-4,-3,3,2] -- [8,-7,8,-13] -- [-4,-12,-13,11] -- [1,2,-12,-8] -- [-4,-16,7,7] -- [16,-17,16,-7] listaNoDivisibles :: Integer -> Integer -> Gen [Integer] listaNoDivisibles _ 0 = return [] listaNoDivisibles p n = do x <- suchThat arbitrary (\i -> i `mod` p /= 0) xs <- listaNoDivisibles p (n-1) return (x:xs) -- (tieneSumaMultiplo n xs) se verifica si algún elemento de (sumas xs) -- es un múltiplo de n. Por ejemplo, -- tieneSumaMultiplo 5 [2,3] == True -- tieneSumaMultiplo 4 [2,3] == False tieneSumaMultiplo n xs = or [s `mod` n == 0 | s <- sumas xs] -- La comprobación es -- λ> quickCheck prop_sumas -- +++ OK, passed 100 tests. |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>