Subsucesiones cuya suma de sus cuadrados es divisible por la longitud de la sucesión

PorJosé A. Alonso 5-junio-20175-junio-2017

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

   subsucesionesE :: [Int] -> [[Int]]

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,

   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]]

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″]

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.

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

albcercid dice:

5-junio-2017 a las 14:50

Haskell

subsucesionesE :: [Int] -> [[Int]] subsucesionesE xs = tail $ filter (\x -> mod (sum (map (^2) x)) t == 0) $ subsequences xs where t = length xs

1
2
3
4

subsucesionesE :: [Int] -> [[Int]]
subsucesionesE xs =
tail $ filter (\x -> mod (sum (map (^2) x)) t == 0) $ subsequences xs
where t = length xs

Responder

subsucesionesE :: [Int] -> [[Int]]
subsucesionesE xs = auxilio a xs
 where a = length xs
       op = sum . map (^2)
       condicion = (\ys -> if ys == [] then False else (op ys) `mod` a == 0)
       auxilio a = filter condicion . subsequences

subsucesionesE :: [Int] -> [[Int]]

subsucesionesE xs = auxilio a xs

where a = length xs

op = sum . map (^2)

condicion = (\ys -> if ys == [] then False else (op ys) `mod` a == 0)

auxilio a = filter condicion . subsequences

Responder

import Data.List
import Test.QuickCheck

subsucesionesE :: [Int] -> [[Int ]]
subsucesionesE xs =(tail
                  . map (map (floor . sqrt . fromIntegral))
                  . filter ((0 ==) . (`mod` l) . sum)
                  . subsequences
                  . map (^2) ) xs
                  where l = length xs

prop_subsucesionesE :: [Int] -> Property
prop_subsucesionesE xs = (not . null) xs ==>  (not . null . subsucesionesE) xs

-- *Main> quickCheck prop_subsucesionesE
-- +++ OK, passed 100 tests.
-- (0.15 secs, 2,751,328 bytes)

import Data.List

import Test.QuickCheck

subsucesionesE :: [Int] -> [[Int ]]

subsucesionesE xs =(tail

. map (map (floor . sqrt . fromIntegral))

. filter ((0 ==) . (`mod` l) . sum)

. subsequences

. map (^2) ) xs

where l = length xs

prop_subsucesionesE :: [Int] -> Property

prop_subsucesionesE xs = (not . null) xs ==> (not . null . subsucesionesE) xs

-- *Main> quickCheck prop_subsucesionesE

-- +++ OK, passed 100 tests.

-- (0.15 secs, 2,751,328 bytes)

Responder

subsucesionesE :: [Int] -> [[Int]]
subsucesionesE xs = [ ys | ys <- subsequences xs, sum (map (^2) ys) `mod` length xs == 0, ys /= []]

prop_subsucesionesE :: [Int] -> Property
prop_subsucesionesE xs = ( xs /= []) ==> (subsucesionesE xs /= [])

subsucesionesE :: [Int] -> [[Int]]

subsucesionesE xs = [ ys | ys <- subsequences xs, sum (map (^2) ys) `mod` length xs == 0, ys /= []]

prop_subsucesionesE :: [Int] -> Property

prop_subsucesionesE xs = ( xs /= []) ==> (subsucesionesE xs /= [])

Responder

subsucesionesE :: [Int] -> [[Int]]
subsucesionesE xs = filter (/= []) (aux (subsequences xs))
    where aux [] = []
          aux (ys:yss) | sum (map (^2) ys) `mod`(length xs) == 0 = ys:aux yss
                       | otherwise = aux yss

subsucesionesE :: [Int] -> [[Int]]

subsucesionesE xs = filter (/= []) (aux (subsequences xs))

where aux [] = []

aux (ys:yss) | sum (map (^2) ys) `mod`(length xs) == 0 = ys:aux yss

| otherwise = aux yss

Responder

import Data.List (permutations,nub,sort)
import Test.QuickCheck

subsucesionesE :: [Int] -> [[Int]]
subsucesionesE xs = tail $ nub [ as | as <- [ take k zs | zs <- subsucesiones xs
                                                         , k <- [1..n]]
                                     , sum (map (^2) as) `mod` n == 0]
                where n = length xs

subsucesiones :: [a] -> [[a]]
subsucesiones [] = [[]]
subsucesiones (x:xs) = sb ++ map (x:) sb
              where sb = subsucesiones xs


prop_sub :: [Int] -> Property
prop_sub xs = (not . null) xs ==> (not . null . subsucesionesE) xs

import Data.List (permutations,nub,sort)

import Test.QuickCheck

subsucesionesE :: [Int] -> [[Int]]

subsucesionesE xs = tail $ nub [ as | as <- [ take k zs | zs <- subsucesiones xs

, k <- [1..n]]

, sum (map (^2) as) `mod` n == 0]

where n = length xs

subsucesiones :: [a] -> [[a]]

subsucesiones [] = [[]]

subsucesiones (x:xs) = sb ++ map (x:) sb

where sb = subsucesiones xs

prop_sub :: [Int] -> Property

prop_sub xs = (not . null) xs ==> (not . null . subsucesionesE) xs

Responder

import Data.List

subsucesionesE :: [Int] -> [[Int]]
subsucesionesE xss = [x| x <- (subsequences xss), (sum (map (^2) x)) `mod` n == 0, not (null x)]
   where n = length xss

import Data.List

subsucesionesE :: [Int] -> [[Int]]

subsucesionesE xss = [x| x <- (subsequences xss), (sum (map (^2) x)) `mod` n == 0, not (null x)]

where n = length xss

Responder

alCuadrado [[]] = [[]]
alCuadrado [xs] = [map (^2) xs]
alCuadrado (xs:xss) = [map (^2) xs] ++ alCuadrado xss

suma :: [[Int]] -> [Int]
suma [[]] = []
suma [xs] = [sum(xs)]
suma (xs:xss) = [sum(xs)] ++ suma xss

quitar :: [Int] -> Int
quitar [] = 0
quitar [x] = x
quitar (x:xs) = x + quitar xs

subsucesionesE :: [Int] -> [[Int]]
subsucesionesE xs = tail [ys | ys <- subsequences xs, quitar(suma(alCuadrado [ys])) `mod` (length xs) == 0]

alCuadrado [[]] = [[]]

alCuadrado [xs] = [map (^2) xs]

alCuadrado (xs:xss) = [map (^2) xs] ++ alCuadrado xss

suma :: [[Int]] -> [Int]

suma [[]] = []

suma [xs] = [sum(xs)]

suma (xs:xss) = [sum(xs)] ++ suma xss

quitar :: [Int] -> Int

quitar [] = 0

quitar [x] = x

quitar (x:xs) = x + quitar xs

subsucesionesE :: [Int] -> [[Int]]

subsucesionesE xs = tail [ys | ys <- subsequences xs, quitar(suma(alCuadrado [ys])) `mod` (length xs) == 0]

Responder

import Data.List
import Test.QuickCheck

subsucesionesE :: [Int] -> [[Int]]
subsucesionesE xs = [ys |ys <- subsequences xs
                        ,sum (map (^2) ys) `rem` length xs == 0
                        ,not (null ys)]

prop_subsucesionesE :: [Int] -> Property
prop_subsucesionesE xs = not (null xs)  ==> not (null (subsucesionesE xs))

import Data.List

import Test.QuickCheck

subsucesionesE :: [Int] -> [[Int]]

subsucesionesE xs = [ys |ys <- subsequences xs

,sum (map (^2) ys) `rem` length xs == 0

,not (null ys)]

prop_subsucesionesE :: [Int] -> Property

prop_subsucesionesE xs = not (null xs) ==> not (null (subsucesionesE xs))

Responder

Subsucesiones cuya suma de sus cuadrados es divisible por la longitud de la sucesión

Soluciones

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico