Casas con números equilibrados
Continuando con los problema propuestos por alumnos, el de hoy es el propuesto por Rafael Jiménez.
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 |
1 + 2 + 3 + 4 + 5 = 7 + 8 |
Definir la función
1 |
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,
1 2 3 4 5 6 |
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
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 |
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: -- ghci> 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, -- ghci> 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 -- ghci> quickCheck prop_soluciones -- +++ OK, passed 100 tests. -- Comparación de eficiencia: -- ghci> soluciones1 1 2000 -- [(1,1),(6,8),(35,49),(204,288),(1189,1681)] -- (337.30 secs, 396493594456 bytes) -- ghci> soluciones2 1 2000 -- [(1,1),(6,8),(35,49),(204,288),(1189,1681)] -- (23.47 secs, 3859436176 bytes) -- ghci> soluciones3 1 2000 -- [(1,1),(6,8),(35,49),(204,288),(1189,1681)] -- (0.01 secs, 1029592 bytes) |
Imponiendo la condición de las sumas y despejando, se obtiene que el numero de la casa es a = sqrt (n(n+1)/2), luego solo existirá cuando n(n+1)/2 sea un cuadrado perfecto.
ligeramente mejor