Subsucesiones cuya suma de sus cuadrados es divisible por la longitud de la sucesión
El enunciado de un problema para la IMO (Olimpiada Internacional de Matemáticas) de 1966 es
Sea a(1),…,a(n) (n ≥ 2) una sucesión de enteros. Demostrar que existe una subsucesión 1 ≤ k(1) < k(2) < ··· < k(m) ≤ n, tal que a(k(1))^2 + ... + a(k(m))^2 es divisible por n.
Definir la función
1 |
subsucesionesE :: [Int] -> [[Int]] |
tal que (subsucesionesE xs) es la lista de las subsucesiones de xs tales que la suma de sus cuadrados es divisible por la longitud de xs. Por ejemplo,
1 2 3 4 5 |
subsucesionesE [3,2,9] == [[3],[9],[3,9]] subsucesionesE [3,2,1] == [[3]] subsucesionesE [5,2,1] == [[5,2,1]] subsucesionesE [3,9,6,4,1] == [[3,9],[3,6],[3,4],[3,1]] subsucesionesE [1,9,6,4,3] == [[1,3],[9,3],[6,3],[4,3]] |
Comprobar con QuickCheck que toda lista no vacía xs tiene alguna subsucesión ys tal que la suma de los cuadrados de los elementos de ys es divisible por la longitud de xs.
Soluciones
[schedule expon=’2017-06-12′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 12 de junio.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
[/schedule]
[schedule on=’2017-06-12′ at=»06:00″]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import Data.List (subsequences) import Test.QuickCheck subsucesionesE :: [Int] -> [[Int]] subsucesionesE xs = [ys | ys <- tail (subsequences xs), sum [y^2 | y <- ys] `rem` length xs == 0] -- La propiedad es prop_subsucesionesE :: [Int] -> Property prop_subsucesionesE xs = not (null xs) ==> not (null (subsucesionesE xs)) -- La comprobación es -- λ> quickCheck prop_subsucesionesE -- +++ OK, passed 100 tests. |
[/schedule]
9 Comentarios