Biparticiones con la misma suma
El enunciado del problema 1 de la Fase Local de la Olimpiada Matemática Española del 2010 es
Sea I(n) el conjunto de los n primeros números naturales impares. Por ejemplo: I(3) = {1,3,5}, I(6) = {1,3,5,7,9,11}, etc.
¿Para qué números n el conjunto I(n) se puede descomponer en dos partes (disjuntas) de forma que coincidan las sumas de los números en cada una de ellas?
Definir las funciones
1 2 3 |
biparticiones :: Integer -> [([Integer],[Integer])] tieneBiparticiones :: Integer -> Bool biparticionD :: Integer -> Maybe ([Integer],[Integer]) |
tales que
- (biparticiones n) es la lista de las biparticiones de I(n) con igual suma; es decir, la lista de los pares (xs,ys) tales que xs e ys son subconjuntos disjuntos de I(n) cuya unión es I(n) y la suma de los elementos de xs es igual que la de los de ys. Por ejemplo,
1 2 3 4 5 6 |
λ> biparticiones 4 [([1,7],[3,5])] λ> biparticiones 5 [] λ> biparticiones 8 [([1,3,13,15],[5,7,9,11]),([1,5,11,15],[3,7,9,13]),([1,7,9,15],[3,5,11,13]),([1,7,11,13],[3,5,9,15])] |
- (tieneBiparticiones n) se verifica si I(n) tiene alguna bipartición con igual suma. Por ejemplo,
1 2 3 |
tieneBiparticiones 4 == True tieneBiparticiones 5 == False tieneBiparticiones (10^(10^7)) == True |
- (biparticionD n) es una de las biparticiones de I(n) con igual suma, si tiene alguna y Nothing, en caso contrario. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> biparticionD 6 Just ([7,11],[1,3,5,9]) λ> biparticionD 7 Nothing λ> biparticionD 8 Just ([1,7,9,15],[3,5,11,13]) λ> biparticionD 10 Just ([7,11,13,19],[1,3,5,9,15,17]) λ> biparticionD 12 Just ([1,7,9,15,17,23],[3,5,11,13,19,21]) λ> biparticionD 30 Just ([7,11,13,19,21,27,29,35,37,43,45,51,53,59],[1,3,5,9,15,17,23,25,31,33,39,41,47,49,55,57]) λ> length (show (biparticionD (2*10^4))) 114455 |
Usando tieneBiparticiones calcular los 10 primeros valores buscados (es decir, los 10 valores de n para los que I(n) se puede descomponer en dos partes (disjuntas) de forma que coincidan las sumas de los números en cada una de ellas) y generalizar.
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 113 114 115 |
import Data.List ((\\), delete, genericTake, sort, subsequences) import Data.Maybe (listToMaybe) import Test.QuickCheck (Property, (==>), quickCheck) -- 1ª definición de biparticiones -- ================================= biparticiones :: Integer -> [([Integer],[Integer])] biparticiones n = ordena [(bs \\ as,as) | as <- genericTake (2^(n-1)) (subsequences bs), 2 * sum as == m] where bs = genericTake n impares m = sum bs -- impares es la lista de los números impares. Por ejemplo, -- take 9 impares == [1,3,5,7,9,11,13,15,17] impares :: [Integer] impares = [1,3..] -- (ordena ps) es lista obtenida poniendo en primer lugar la menor de -- las componentes de los pares de ps y ordenando el resultado. Por -- ejemplo, -- ordena [(5,3),(1,7),(4,2)] == [(1,7),(2,4),(3,5)] ordena :: Ord a => [(a,a)] -> [(a,a)] ordena ps = sort (map aux ps) where aux (xs,ys) | xs < ys = (xs,ys) | otherwise = (ys,xs) -- 2ª definición de biparticiones -- ================================= biparticiones2 :: Integer -> [([Integer],[Integer])] biparticiones2 n = sort (aux ([([a], delete a bs) | a <- bs])) where bs = genericTake n impares m = sum bs aux [] = [] aux ((_,[]):ps) = aux ps aux ((xs,ys):ps) | sum xs == sum ys = if xs < ys then (xs,ys) : aux ps else aux ps | sum xs < sum ys = aux ([(a:xs, delete a ys) | a <- ys, a < head xs] ++ ps) | otherwise = aux ps -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_biparticiones :: Integer -> Bool prop_biparticiones n = and [biparticiones k == biparticiones2 k | k <- [1..n]] -- La comprobación es -- λ> prop_biparticiones 20 -- True -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (biparticiones 20) -- 3965 -- (0.36 secs, 568,151,296 bytes) -- λ> length (biparticiones2 20) -- 3965 -- (2.51 secs, 2,490,876,672 bytes) -- λ> head (biparticiones 20) -- ([1,3,5,7,9,11,13,15,17,19,21,23,25,31],[27,29,33,35,37,39]) -- (0.37 secs, 562,477,968 bytes) -- λ> head (biparticiones2 20) -- ([1,3,5,7,9,11,13,15,17,19,21,23,25,31],[27,29,33,35,37,39]) -- (2.33 secs, 2,488,098,776 bytes) -- 1ª definición de tieneBiparticiones -- ====================================== tieneBiparticiones :: Integer -> Bool tieneBiparticiones = not . null . biparticiones -- 2ª definición de tieneBiparticiones -- ====================================== -- Observando el siguiente cálculo -- λ> [n | n <- [1..20], tieneBiparticiones n] -- [4,6,8,10,12,14,16,18,20] tieneBiparticiones2 :: Integer -> Bool tieneBiparticiones2 n = n > 3 && even n -- 1ª definición de biparticionD -- ================================ biparticionD :: Integer -> Maybe ([Integer],[Integer]) biparticionD = listToMaybe . biparticiones -- 2ª definición de biparticionD -- ================================ biparticionD2 :: Integer -> Maybe ([Integer],[Integer]) biparticionD2 x | x < 4 || odd x = Nothing | otherwise = Just (aux x) where aux 4 = ([1,7],[3,5]) aux 6 = ([7,11],[1,3,5,9]) aux n = (xs ++ [m+1,m+7], ys ++ [m+3,m+5]) where (xs,ys) = aux (n-4) m = 2*(n-4) -- Cálculo de la respuesta -- ======================= -- El cálculo es -- λ> take 10 [n | n <- [1..], tieneBiparticiones n] -- [4,6,8,10,12,14,16,18,20,22] -- cuyos valores son los números pares mayores que 3. |
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>
No se me ocurre una forma más sucinta de mostrar cómo construir cualquier solución con coste O(n)