Menu Close

Conjuntos con más sumas que restas

José A. Alonso,

Dado un conjunto de números naturales, por ejemplo A = {0, 2, 3, 4}, calculamos las sumas de todos los pares de elementos de A. Como A tiene 4 elementos hay 16 pares, pero no todas sus sumas son distintas. En este caso solo hay 8 sumas distintas: {0, 2, 3, 4, 5, 6, 7, 8}. Procediendo análogamente hay 9 diferencias distinatas entre los pares de A: {-4, -3, -2, -1, 0, 1, 2, 3, 4}.

Experimentando con más conjuntos, se puede conjeturar que el número de restas es mayor que el de sumas y argumentar que que mientras que con dos números distintos sólo se produce una suma distints sin embargo se producen dos restas distintas. Por ejemplo, con 5 y 7 sólo se produce una suma (ya que 5+7 y 7+5 ambos dan 12) pero dos restas (ya que 5-7 y 7-5 dan -2 y 2, respectivamente).

Sin embargo, la conjetura es falsa. Un contraejemplo en el conjunto {0, 2, 3, 4, 7, 11, 12, 14}, que tiene 26 sumas distintas con sus pares de elementos pero sólo 25 restas.

Los conjuntos con más sumas distintas con sus pares de elementos que restas se llaman conjuntos MSQR (por “más sumas que restas”).

El objetivo de este ejercicio es calcular los conjuntos MSQR.

Definir las funciones

   tieneMSQR :: [Integer] -> Bool
   conjuntosMSQR :: [[Integer]]

tales que

  • (tieneMSQR xs) se verifica si el conjunto xs tiene más sumas que restas. Por ejemplo,
     tieneMSQR [0, 2, 3, 4]                 ==  False
     tieneMSQR [0, 2, 3, 4, 7, 11, 12, 14]  ==  True
  • conjuntosMSQR es la lista de los conjuntos MSQR. Por ejemplo,
     λ> take 5 conjuntosMSQR
     [[14,12,11,7,4,3,2,0],
      [14,12,11,10,7,3,2,0],
      [14,13,12,9,5,4,2,1,0],
      [14,13,12,10,9,5,2,1,0],
      [15,13,12,8,5,4,3,1]]
 
      length (takeWhile (< [14]) conjuntosMSQR)   ==  0
      length (takeWhile (< [15]) conjuntosMSQR)   ==  4
      length (takeWhile (< [16]) conjuntosMSQR)   ==  10
      length (takeWhile (< [17]) conjuntosMSQR)   ==  30

Soluciones

import Data.List (tails, nub, sort)
 
-- 1ª solución
-- ===========
 
-- (sumas xs) es el conjunto de las sumas de pares de elementos de
-- xs. Por ejemplo,
--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]
sumas :: [Integer] -> [Integer]
sumas xs = nub [x + y | x <- xs, y <- xs]
 
-- (restas xs) es el conjunto de las restas de pares de elementos de
-- xs. Por ejemplo,
--    restas [0,2,3,4]  ==  [0,-2,-3,-4,2,-1,3,1,4]
restas :: [Integer] -> [Integer]
restas xs = nub [x - y | x <- xs, y <- xs]
 
tieneMSQR :: [Integer] -> Bool
tieneMSQR xs = length (sumas xs) > length (restas xs)
 
conjuntosMSQR :: [[Integer]]
conjuntosMSQR = [xs | xs <- enumeracionCFN, tieneMSQR xs]
 
-- enumeracionCFN es la enumeración de los conjuntos finitos de números
-- naturales del ejercicio anterior.
enumeracionCFN :: [[Integer]]
enumeracionCFN = concatMap enumeracionCFNHasta [0..]
 
-- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeración
-- anterior cuyo primer elemento es n. Por ejemplo,
--    λ> enumeracionCFNHasta 1
--    [[1],[1,0]]
--    λ> enumeracionCFNHasta 2
--    [[2],[2,0],[2,1],[2,1,0]]
--    λ> enumeracionCFNHasta 3
--    [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]]
enumeracionCFNHasta :: Integer -> [[Integer]]
enumeracionCFNHasta 0 = [[],[0]]
enumeracionCFNHasta n =
  [n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k]
 
-- 2ª solución
-- ===========
 
-- (sumas2 xs) es el conjunto de las sumas de pares de elementos de
-- xs. Por ejemplo,
--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]
--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]
sumas2 :: [Integer] -> [Integer]
sumas2 xs = nub [x + y | (x:ys) <- tails xs, y <- (x:ys)]
 
-- (restas2 xs) es el conjunto de las restas de pares de elementos de
-- xs. Por ejemplo,
--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]
--    restas2 [0,2,3,4]  ==  [0,-2,-3,-4,2,-1,3,1,4]
restas2 :: [Integer] -> [Integer]
restas2 xs = 0 : ys ++ map negate ys
  where ys = nub [x - y | (x:ys) <- tails (sort xs), y <- ys]
 
tieneMSQR2 :: [Integer] -> Bool
tieneMSQR2 xs = length (sumas2 xs) > length (restas2 xs)
 
conjuntosMSQR2 :: [[Integer]]
conjuntosMSQR2 = [xs | xs <- enumeracionCFN, tieneMSQR2 xs]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> length (takeWhile (< [17,16..0]) conjuntosMSQR)
--    66
--    (21.36 secs, 10,301,222,168 bytes)
--    λ> length (takeWhile (< [17,16..0]) conjuntosMSQR2)
--    66
--    (10.13 secs, 7,088,969,752 bytes)

Pensamiento

¡Qué fácil es volar, qué fácil es!
Todo consiste en no dejar que el suelo
se acerque a nuestros pies.

Antonio Machado

Avanzado
, , , , , , , ,

5 soluciones de “Conjuntos con más sumas que restas”

  1. Responder
    claniecas 
    import Data.List (nub, sort)
 
tieneMSQR :: [Integer] -> Bool
tieneMSQR xs = length (suma xs) > length (resta xs)
  where suma  xs = nub (sort [x+y | x <- xs, y <- xs])
        resta xs = nub (sort [x-y | x <- xs, y <- xs])
  2. Responder
    goncarmar1 
    import Data.List
 
tieneMSQR :: [Integer] -> Bool
tieneMSQR xs = cuantasS xs > cuantasR xs
 
conjuntosMSQR :: [[Integer]]
conjuntosMSQR = [xs | xs <- decrecientes , tieneMSQR xs]
 
decrecientes :: [[Integer]]
decrecientes = concat [decreciente n | n <- [0,1..]]
 
decreciente :: Integer -> [[Integer]]
decreciente n
  | n < 0     = []
  | n == 0    = [[0]]
  | otherwise = [n] : map (n:) (concat [decreciente n | n <- [0,1..n-1]])
 
cuantasS :: [Integer] -> Int
cuantasS = length . nub . sumaC
 
sumaC :: [Integer] -> [Integer]
sumaC [x]    = [x+x]
sumaC (x:xs) = [x + y | y <- (x:xs)] ++ [y + x | y <- (x:xs)] ++ sumaC xs
 
cuantasR :: [Integer] -> Int
cuantasR = length . nub. restaC
 
restaC :: [Integer] -> [Integer]
restaC [x] = [0]
restaC (x:xs) = [x - y | y <- (x:xs)] ++ [y - x | y <- (x:xs)] ++ restaC xs
 
-- Aunque es capaz de calcular todo, podría ser más eficiente
--    λ> length (takeWhile (< [17]) conjuntosMSQR) 
--    30
--    (16.47 secs, 5,837,687,528 bytes)
  3. Responder
    enrzubgon 
    import Data.List
 
tieneMSQR :: [Integer] -> Bool
tieneMSQR xs = length (sumas xs) > length (restas xs)
  where sumas xs  = nub [x+y | (x,y) <- [(x,y) | x <- xs, y <- xs]]
        restas xs = nub [x-y | (x,y) <- [(x,y) | x <- xs, y <- xs]]
 
conjuntosMSQR :: [[Integer]]
conjuntosMSQR = filter (tieneMSQR) (subsequences [0..])
  4. Responder
    enrzubgon

    Hago una pequeña corrección a la solución subida anteriormente para que las listas se ordenen de mayor a menor, igual que en el enunciado

    import Data.List
 
tieneMSQR :: [Integer] -> Bool
tieneMSQR xs = length (sumas xs) > length (restas xs)
  where sumas xs  = nub [x+y | (x,y) <- [(x,y) | x <- xs, y <- xs]]
        restas xs = nub [x-y | (x,y) <- [(x,y) | x <- xs, y <- xs]]
 
conjuntosMSQR :: [[Integer]]
conjuntosMSQR = map reverse (filter tieneMSQR (subsequences [0..]))
  5. Responder
    javjimord 
    import Data.List (nub, subsequences)
 
tieneMSQR :: [Integer] -> Bool
tieneMSQR xs = length (sumas xs) > length (restas xs)
 
sumas :: [Integer] -> [Integer]
sumas xs = nub [x+y | x <- xs, y <- xs]
 
restas :: [Integer] -> [Integer]
restas xs = nub [x-y | x <- xs, y <- xs]
 
conjuntosMSQR :: [[Integer]]
conjuntosMSQR =
  [reverse xs | xs <- subsequences [0..] , tieneMSQR xs]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.