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.

-- ---------------------------------------------------------------------
-- § 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]

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]

Se puede imprimir o compartir con