Menu Close

Día: 12 mayo, 2021

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

   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,
     λ> 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,
     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,
     λ> 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

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>