Meses: diciembre 2012

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell de un problema propuesto para la Olimpiada Internacional de Matemáticas de 1982 cuyo enunciado es

Calcular la suma de todos los enteros positivos cuyos dígitos forman una sucesión estrictamente creciente o estrictamente decreciente.

Lo resolveremos generando las listas de todos los enteros positivos cuyos dígitos forman una sucesión estrictamente monótona. Para ello nos basaremos en las listas de dígitos que forman una sucesión estrictamente monótona.

Comenzamos con los decrecientes:

• (listasDecrecientesDesde n) es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es n. Por ejemplo,
  ghci> listasDecrecientesDesde 3
  [[3],[3,2],[3,2,1],[3,2,1,0],[3,2,0],[3,1],[3,1,0],[3,0]]
  
  Haskell

  listasDecrecientesDesde :: Integer -> [[Integer]] listasDecrecientesDesde 0 = [[0]] listasDecrecientesDesde n = [n] : [n:ys | m <- [n-1,n-2..0], ys <- listasDecrecientesDesde m]

  1 2 3 4

  listasDecrecientesDesde :: Integer -> [[Integer]] listasDecrecientesDesde 0 = [[0]] listasDecrecientesDesde n =     [n] : [n:ys | m <- [n-1,n-2..0], ys <- listasDecrecientesDesde m]

• listasDecrecientes es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es un dígito. Por ejemplo,
  ghci> take 10 listasDecrecientes
  [[0],[1],[1,0],[2],[2,1],[2,1,0],[2,0],[3],[3,2],[3,2,1]]
  
  Haskell

  listasDecrecientes :: [[Integer]] listasDecrecientes = concat [listasDecrecientesDesde n | n <- [0..9]]

  1 2 3

  listasDecrecientes :: [[Integer]] listasDecrecientes =     concat [listasDecrecientesDesde n | n <- [0..9]]

• (listaNumero xs) es el número correspondiente a la lista de dígitos xs. Por ejemplo,
  listaNumero [3,2,5] == 325
  
  Haskell

  listaNumero :: [Integer] -> Integer listaNumero xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]

  1 2	listaNumero :: [Integer] -> Integer listaNumero xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]

• numerosDecrecientes es la lista de los enteros positivos cuyos dígitos forman una sucesión estrictamente decreciente. Por ejemplo,
  ghci> take 17 numerosDecrecientes
  [0,1,10,2,21,210,20,3,32,321,3210,320,31,310,30,4,43]
  
  Haskell

  numerosDecrecientes :: [Integer] numerosDecrecientes = [listaNumero xs | xs <- listasDecrecientes]

  1 2	numerosDecrecientes :: [Integer] numerosDecrecientes = [listaNumero xs | xs <- listasDecrecientes]

  Análogamente se construyen los crecientes:

• (listasCrecientesDesde n) es la lista de las sucesiones estrictamente crecientes cuyo primer elemento es n. Por ejemplo,
  ghci> listasCrecientesDesde 6
  [[6],[6,7],[6,7,8],[6,7,8,9],[6,7,9],[6,8],[6,8,9],[6,9]]
  
  Haskell

  listasCrecientesDesde :: Integer -> [[Integer]] listasCrecientesDesde 9 = [[9]] listasCrecientesDesde n = [n] : [n:ys | m <- [n+1..9], ys <- listasCrecientesDesde m]

  1 2 3 4

  listasCrecientesDesde :: Integer -> [[Integer]] listasCrecientesDesde 9 = [[9]] listasCrecientesDesde n =     [n] : [n:ys | m <- [n+1..9], ys <- listasCrecientesDesde m]

• listascrecientes es la lista de las sucesiones estrictamente crecientes cuyo primer elemento es un dígito. Por ejemplo,
  ghci> take 5 listasCrecientes
  [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]]
  
  Haskell

  listasCrecientes :: [[Integer]] listasCrecientes = concat [listasCrecientesDesde n | n <- [1..9]]

  1 2 3

  listasCrecientes :: [[Integer]] listasCrecientes =     concat [listasCrecientesDesde n | n <- [1..9]]

• numerosCrecientes es la lista de los enteros positivos cuyos dígitos forman una sucesión estrictamente creciente. Por ejemplo,
  ghci> take 5 numerosCrecientes
  [1,12,123,1234,12345]
  
  Haskell

  numerosCrecientes :: [Integer] numerosCrecientes = [listaNumero xs | xs <- listasCrecientes]

  1 2	numerosCrecientes :: [Integer] numerosCrecientes = [listaNumero xs | xs <- listasCrecientes]

  Con las definiciones anteriores la solución es inmediata:

  Haskell

  solucion :: Integer solucion = sum (numerosCrecientes ++ numerosDecrecientes) - sum [1..9]

  1 2 3

  solucion :: Integer solucion =     sum (numerosCrecientes ++ numerosDecrecientes) - sum [1..9]

  El cálculo de la solución es

  ghci> solucion 25617208995

  1 2	ghci> solucion 25617208995