Casas con números equilibrados

José A. Alonso

14-04-2015

Se tiene una calle en la que las casas sólo están en un lado de ésta y las casas están numeradas de 1 hasta n, donde n es el número total de casas en la calle. Se dice que el número de una casa es equilibrado si y solamente si la suma de los números de las casas anteriores es igual a la suma de los números posteriores a la casa. Por ejemplo, el número de la 6ª casa, en una calle con 8 casas, es equilibrado ya que

1 + 2 + 3 + 4 + 5 = 7 + 8

Definir la función

soluciones :: Integer -> Integer -> [(Integer,Integer)]

tal que (soluciones x y) es la lista de pares (a,n) tales que a es el número equilibrado de una casa en una calle con n casas y n está entre x e y. Por ejemplo,

soluciones 1 500          ==  [(1,1),(6,8),(35,49),(204,288)]
soluciones 1000 3000      ==  [(1189,1681)]
soluciones (10^5) (10^6)  ==  [(235416,332928)]
soluciones (10^6) (10^7)  ==  [(1372105,1940449)]
(fst $ head $ soluciones (10^100) (10^101))  `mod` (10^9)  ==  763728460
(fst $ head $ soluciones (10^800) (10^1000)) `mod` (10^9)  ==  311156546

Soluciones

import Test.QuickCheck

-- 1ª solución
-- ===========

soluciones1 :: Integer -> Integer -> [(Integer,Integer)]
soluciones1 x y =
    [(n,n+m) | n <- [x..y], m <- [0..y-n],
               sum [1..n-1] == sum [n+1..n+m]]

-- 2ª solución
-- ===========

soluciones2 :: Integer -> Integer -> [(Integer,Integer)]
soluciones2 x y =
    [(n,n+m) | n <- [x..y], m <- [0..y-n],
               esSolucion (n,n+m)]

esSolucion :: (Integer,Integer) -> Bool
esSolucion (n,m) = suma (n-1) == suma m - suma n
    where suma n = n*(n+1) `div` 2

-- 3ª solución
-- ===========

-- Con las definiciones anteriores se pueden calcular los cuatro
-- primeros números de las casas equilibradas:
--    λ> map fst (soluciones2 1 500)
--    [1,6,35,204]
-- Conjeturando que el n-ésimo número p(n) se calcula mediante una
-- recurrencia del tipo p(n) = x*p(n-1) + y*p(n-2) se tiene
--    p(1) =   1
--    p(2) =   6
--    p(3) =  35 =  6x +  y
--    p(4) = 204 = 35x + 6y
-- al resolverlo se obtiene x = 6 e y = -1. Por tanto,
--    p(1) = 1
--    p(2) = 6
--    p(n) = 6*p(n-1) - p(n-2)
--
-- Haciendo lo mismo con las segundas componentes,
--    λ> map snd (soluciones2 1 2000)
--    [1,8,49,288,1681]
-- Conjeturando que el n-ésimo número s(n) se calcula mediante una
-- recurrencia del tipo s(n) = x*s(n-1) + y*s(n-2) + z se tiene
--    s(1) =    1
--    s(2) =    8
--    s(3) =   49 =   8x +   y + z
--    s(4) =  288 =  49x +  8y + z
--    s(5) = 1681 = 288x + 49y + z
-- al resolverlo se obtiene x = 6, y = -1, z = 2. Por tanto,
--    s(1) = 1
--    s(2) = 8
--    s(n) = 6*s(n-1) - s(n-2) + 2

-- El número de la n-ésimo casa equilibrada, p(n), se puede calcular por
-- recursión:
casa :: Integer -> Integer
casa 1 = 1
casa 2 = 6
casa n = 6 * (casa (n-1)) - (casa (n-2))

-- La sucesión de los números de las casas equilibradas se puede
-- calcular por programación dinámica:
casas :: [Integer]
casas =
    1 : 6 : zipWith (\x y -> 6*x-y) (tail casas) casas

-- El número de casas en la n-ésima calle con casas equilibradas, s(n),
-- se puede calcular por recursión:
calle :: Integer -> Integer
calle 1 = 1
calle 2 = 8
calle n = 6 * (calle (n-1)) - (calle (n-2)) + 2

-- La sucesión de los números de las casas equilibradas se puede
-- calcular por programación dinámica:
calles :: [Integer]
calles =
    1 : 8 : zipWith (\x y -> 6*x-y+2) (tail calles) calles

-- Usando casas se obtiene la 3ª solución:
soluciones3 :: Integer -> Integer -> [(Integer,Integer)]
soluciones3 x y =
   takeWhile (<=(y,y)) (dropWhile (<(x,x)) (zip casas calles))

-- Comprobación de soluciones
-- ==========================

-- La propiedad es
prop_soluciones :: Integer -> Integer -> Property
prop_soluciones x y =
    0 < x && x <= y ==>
    all esSolucion (soluciones3 x y)

-- La comprobación es
--    λ> quickCheck prop_soluciones
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia:
--    λ> soluciones1 1 2000
--    [(1,1),(6,8),(35,49),(204,288),(1189,1681)]
--    (337.30 secs, 396493594456 bytes)
--    λ> soluciones2 1 2000
--    [(1,1),(6,8),(35,49),(204,288),(1189,1681)]
--    (23.47 secs, 3859436176 bytes)
--    λ> soluciones3 1 2000
--    [(1,1),(6,8),(35,49),(204,288),(1189,1681)]
--    (0.01 secs, 1029592 bytes)