Biparticiones con igual suma que producto en Haskell
En Números y algo más … se ha planteado el siguiente problema
¿Es posible dividir todos los números del 1 al 2012 en dos grupos, S y P, tal que la suma de los números de S sea igual al producto de los números que están en P? ¿y si fueran 2011 ó 2013? Si es posible, ¿Cómo estarían formados esos conjuntos?
En la siguiente relación de ejercicios (elaborada para la asignatura de Informática de 1º del Grado en Matemáticas) se resuelve el problema con Haskell.
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 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 |
-- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.List import Test.QuickCheck -- --------------------------------------------------------------------- -- § Ejercicios -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- particiones :: Integer -> [([Integer],[Integer])] -- tal que (particiones n) es una lista de pares de listas (xs,ys) tales -- que xs, ys es una partición de los n primeros números naturales y la -- suma de los elementos xs es igual que el producto de los elementos de -- ys. Por ejemplo, -- ghci> particiones 10 -- [([9,8,7,6,5,3,2],[1,4,10]), -- ([10,9,8,5,4,3,2,1],[6,7]), -- ([10,9,8,6,5,4],[1,2,3,7])] -- Obsérvese que las particiones están ordenadas lexicográficamente en -- sus primeras componentes. -- --------------------------------------------------------------------- particiones :: Integer -> [([Integer],[Integer])] particiones 1 = [] particiones n = aux [n,n-1..1] [] (sum [1..n]) 1 where aux xs ys s p | s == p = [(xs,ys)] | s < p = [] | otherwise = concat [aux (delete x xs) (x:ys) (s-x) (p*x) | x <- xs, null ys || x < head ys, s-x >= p*x] -- --------------------------------------------------------------------- -- Ejercicio 2. Calcular las primeras de las (particiones n) para n -- entre 5 y 12. -- --------------------------------------------------------------------- -- El cálculo es -- ghci> head (particiones 5) -- ([5,3],[1,2,4]) -- ghci> head (particiones 6) -- ([5,4,3],[1,2,6]) -- ghci> head (particiones 7) -- ([7,5,4,2],[1,3,6]) -- ghci> head (particiones 8) -- ([7,6,5,4,2],[1,3,8]) -- ghci> head (particiones 9) -- ([9,7,6,5,3,2],[1,4,8]) -- ghci> head (particiones 10) -- ([9,8,7,6,5,3,2],[1,4,10]) -- ghci> head (particiones 11) -- ([11,9,8,7,6,4,3,2],[1,5,10]) -- ghci> head (particiones 12) -- ([11,10,9,8,7,6,4,3,2],[1,5,12]) -- --------------------------------------------------------------------- -- Ejercicio 3. A la vista de los resultados del ejercicios anterior, -- conjeturar una fórmula para calcular la primera de las particiones. -- Indicación: Fijarse en la segunda componente distiguiendo casos según -- la paridad de n. -- --------------------------------------------------------------------- -- Para n par las segundas componentes de las particiones son -- n | -- ---+---------- -- 6 | [1,2,6] -- 8 | [1,3,8] -- 10 | [1,4,10] -- 12 | [1,5,12] -- La conjetura es que es una terna cuyos elementos son 1, n/2-1 y n. -- -- Para n impar las segundas componentes de las particiones son -- n | -- ---+---------- -- 5 | [1,2,4] -- 7 | [1,3,6] -- 9 | [1,4,8] -- 11 | [1,5,10] -- La conjetura es que es una terna cuyos elementos son 1, (n-1)/2 y -- n-1. -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- particion :: Integer -> ([Integer],[Integer]) -- donde (particion n) es la partición de n calculada usando la -- conjetura del ejercicio anterior. -- --------------------------------------------------------------------- particion :: Integer -> ([Integer],[Integer]) particion n | even n = ([n,n-1..1] \\ pPar, pPar) | otherwise = ([n,n-1..1] \\ pImpar, pImpar) where pPar = [1, n `div` 2 - 1, n] pImpar = [1, (n-1) `div` 2, n-1] -- --------------------------------------------------------------------- -- Ejercicio 5. Comprobar con QuickCheck que, para n >= 5, si el valor -- de (particion n) es (xs,ys), entonces la suma de los elementos de xs -- es igual que el producto de los elementos de ys. -- --------------------------------------------------------------------- -- La propiedad es prop_particion :: Integer -> Property prop_particion n = n >= 5 ==> n*(n+1) `div` 2 - sum ys == product ys where (xs,ys) = particion n -- La comprobación es -- ghci> quickCheck prop_particion -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 6. Demostrar que, para n >= 5, si el valor de (particion n) -- es (xs,ys), entonces la suma de los elementos de xs es igual que el -- producto de los elementos de ys. -- --------------------------------------------------------------------- -- Para n = 2m, se tiene que -- sum xs = sum [1..2m] - sum [1,m-1,2m] -- = 2m(2m+1)/2 - (1+m-1+2m) -- = 2m^2 + m - 3m -- = 2m^2 - 2m -- product ys = 1*(m-1)*2m -- = 2m^2 - 2m -- -- Para n = 2m+1, se tiene que -- sum xs = sum [1..2m+1] - sum [1,m,2m] -- = (2m+1)(2m+2)/2 - (1+m+2m) -- = 2m^2 + 3m + 1 - 1 - 3m -- = 2m^2 -- product ys = 1*m*2m -- = 2m^2 -- --------------------------------------------------------------------- -- Ejercicio 7. Resolver el problema inicial; es decir calcular una -- partición de los números 2011, 2012 y 2013. -- --------------------------------------------------------------------- -- El cálculo de los segundos elementos de las particiones (los primeros -- son los restantes) es -- ghci> snd (particion 2011) -- [1,1005,2010] -- ghci> snd (particion 2012) -- [1,1005,2012] -- ghci> snd (particion 2013) -- [1,1006,2012] |