Menu Close

Ternas aditivas

El enunciado del problema C6 de la Fase Local de la Olimpiada Matemática Española del 2006 es

Decimos que tres números naturales distintos forman una terna aditiva si la suma de los dos primeros de ellos es igual al tercero. Hallar, razonadamente, el máximo número de ternas aditivas que puede haber en un conjunto dado de 20 números naturales.

Definir las funciones

   ternasAditivas  :: Integer -> [(Integer,Integer,Integer)]
   nTernasAditivas :: Integer -> Integer

tales que

  • (ternasAditivas n) es la lista de las ternas aditivas crecientes que se pueden formar con los n primeros números enteros positivos. Por ejemplo,
     λ> ternasAditivas 7
     [(1,2,3),(1,3,4),(1,4,5),(1,5,6),(1,6,7),(2,3,5),(2,4,6),(2,5,7),(3,4,7)]
     λ> length (ternasAditivas (10^4))
     24995000
  • (nTernasAditivas n) es el número de ternas aditivas crecientes que se pueden formar con los n primeros números enteros positivos. Por ejemplo,
     nTernasAditivas 7                            ==  9
     length (show (nTernasAditivas (10^(10^5))))  ==  200000
     length (show (nTernasAditivas (10^(10^6))))  ==  2000000
     length (show (nTernasAditivas (10^(10^7))))  ==  20000000

Soluciones

import Data.List (genericLength)
 
-- 1ª definición de ternasAditivas
-- ===============================
 
ternasAditivas :: Integer -> [(Integer,Integer,Integer)]
ternasAditivas n =
  [(a,b,c) | a <- [1..n],
             b <- [a+1..n],
             let c = a+b,
             c <= n]
 
-- 2ª definición de ternasAditivas
-- ===============================
 
ternasAditivas2 :: Integer -> [(Integer,Integer,Integer)]
ternasAditivas2 n =
  [(a,b,a+b) | a <- [1..n],
               b <- [a+1..n-a]]
 
-- Comprobación de equivalencia
-- ============================
 
-- La comprobación es
--    λ> and [ternasAditivas n == ternasAditivas2 n | n <- [1..300]]
--    True
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (ternasAditivas (5*10^3))
--    6247500
--    (4.02 secs, 2,950,741,752 bytes)
--    λ> length (ternasAditivas2 (5*10^3))
--    6247500
--    (1.15 secs, 1,401,184,264 bytes)
 
-- 1ª definición de nTernasAditivas
-- ================================
 
nTernasAditivas :: Integer -> Integer
nTernasAditivas = genericLength . ternasAditivas
 
-- 2ª definición de nTernasAditivas
-- ================================
 
-- Observando los siguientes cálculos
--    λ> [nTernasAditivas n | n <- [1..20]]
--    [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]
--    λ> [(n-1)^2 `div` 4 | n <- [1..20]]
--    [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]
 
nTernasAditivas2 :: Integer -> Integer
nTernasAditivas2 n = (n-1)^2 `div` 4
 
-- 3ª definición de nTernasAditivas
-- ================================
 
nTernasAditivas3 :: Integer -> Integer
nTernasAditivas3 = (`div` 4) . (^ 2) . pred
 
-- Comprobación de equivalencia
-- ============================
 
-- La comprobación es
--    λ> and [nTernasAditivas n == nTernasAditivas2 n | n <- [1..200]]
--    True
--    λ> and [nTernasAditivas2 n == nTernasAditivas3 n | n <- [1..200]]
--    True
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> nTernasAditivas (5*10^3)
--    6247500
--    (5.66 secs, 3,663,331,112 bytes)
--    λ> nTernasAditivas2 (5*10^3)
--    6247500
--    (0.02 secs, 106,752 bytes)
--    λ> nTernasAditivas3 (5*10^3)
--    6247500
--    (0.02 secs, 106,568 bytes)

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>

Una solución de “Ternas aditivas

  1. Rubén Muñoz Mkrtchian
    import Data.List (genericLength)
    import Test.QuickCheck (quickCheck)
     
    -- Definiciones de ternasAditivas:
    -- ==============================
     
    ternasAditivas1  :: Integer -> [(Integer,Integer,Integer)]
    ternasAditivas1 n = [(a,b,c) | a <- [1..n], b <- [a+1..n], let c = a+b, c <= n] 
     
    ternasAditivas2 :: Integer -> [(Integer,Integer,Integer)]
    ternasAditivas2 n = [(a,b,c) | a <- [1..k], b <- [a+1..n-a], let c = a+b]
      where k = div n 2
     
    -- Equivalencia de las definiciones:
    -- ================================
     
    prop1 :: Integer -> Bool
    prop1 n = ternasAditivas1 m == ternasAditivas2 m
      where m = abs n + 1
     
    -- La comprobación es:
    -- λ> quickCheck prop1
    -- +++ OK, passed 100 tests.
     
    -- Comparación de eficiencia:
    -- =========================
     
    -- λ> length (ternasAditivas1 1500)
    -- 561750
    -- (0.86 secs, 265,750,936 bytes)
    -- λ> length (ternasAditivas2 1500)
    -- 561750
    -- (0.22 secs, 126,136,296 bytes)
    --
    -- λ> length (ternasAditivas4 7500)
    -- 14058750
    -- (4.85 secs, 3,150,451,720 bytes)
     
    ternasAditivas :: Integer -> [(Integer,Integer,Integer)]
    ternasAditivas = ternasAditivas2
     
    -- Definiciones de nTernasAditivas:
    -- ===============================
     
    nTernasAditivas1 :: Integer -> Integer
    nTernasAditivas1 = genericLength . ternasAditivas
     
    -- Vamos a calcular nTernasAditivas1 para los primeros 20 números naturales.
    --    λ> [nTernasAditivas1 n | n <- [1..20]]
    --    [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]
    --
    -- Los términos de van construyendo de la forma 0+0+1+1+2+2+3+3+...
    --    + Si n es par, tenemos un número par de sumandos y el número de ternas
    --    aditivas es el siguiente:
    --       2*(1+2+...+n/2-1)
    --       = 2*((n/2-1)*(n/2-1+1))/2
    --       = n/2*(n-2)/2
    --       = (n(n-2))/4
    --
    --    + Si n es impar, tenemos un número impar de sumandos y el número de
    --    ternas aditivas es el siguiente:
    --       2*(1+2+...+(n-1)/2-1) + (n-1)/2
    --       = 2*(((n-1)/2-1)*((n-1)/2)-1+1)/2 + (n-1)/2
    --       = ((n-1)/2)*((n-3)/2) + (n-1)/2
    --       = ((n-1)/2)*((n-3)/2 + 1)
    --       = ((n-1)/2)^2
     
    nTernasAditivas2 :: Integer -> Integer
    nTernasAditivas2 n
      | even n = div (n*(n-2)) 4
      | odd n  = (div (n-1) 2)^2
     
    -- Equivalencia de las definiciones:
    -- ================================
     
    prop2 :: Integer -> Bool
    prop2 n = nTernasAditivas1 m == nTernasAditivas2 m
      where m = abs n + 1
     
    -- La comprobación es:
    -- λ> quickCheck prop2
    -- +++ OK, passed 100 tests.
     
    -- Comparación de eficiencia:
    -- =========================
     
    -- λ> nTernasAditivas1 5000
    -- 6247500
    -- (3.04 secs, 2,112,905,800 bytes)
    -- λ> nTernasAditivas2 5000
    -- 6247500
    -- (0.00 secs, 60,008 bytes)
    --
    -- λ> length (show (nTernasAditivas2 (10^(10^7))))
    -- 20000000
    -- (3.67 secs, 1,135,725,432 bytes)
     
    nTernasAditivas :: Integer -> Integer
    nTernasAditivas = nTernasAditivas2

Leave a Reply

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