Teorema de existencia de divisores
El teorema de existencia de divisores afirma que
En cualquier subconjunto de {1, 2, ..., 2m} con al menos m+1 elementos existen números distintos a, b tales que a divide a b.
Un conjunto de números naturales xs es mayoritario si existe un m tal que la lista de xs es un subconjunto de {1,2,...,2m} con al menos m+1 elementos. Por ejemplo, {2,3,5,6} porque es un subconjunto de {1,2,...,6} con más de 3 elementos.
Definir las funciones
divisoresMultiplos :: [Integer] -> [(Integer,Integer)] esMayoritario :: [Integer] -> Bool
tales que
- (divisores xs) es la lista de pares de elementos distintos de (a,b) tales que a divide a b. Por ejemplo,
divisoresMultiplos [2,3,5,6] == [(2,6),(3,6)] divisoresMultiplos [2,3,5] == [] divisoresMultiplos [4..8] == [(4,8)]
- (esMayoritario xs) se verifica xs es mayoritario. Por ejemplo,
esMayoritario [2,3,5,6] == True esMayoritario [2,3,5] == False
Comprobar con QuickCheck el teorema de existencia de divisores; es decir, en cualquier conjunto mayoritario existen números distintos a, b tales que a divide a b. Para la comprobación se puede usar el siguiente generador de conjuntos mayoritarios
mayoritario :: Gen [Integer] mayoritario = do m' <- arbitrary let m = 1 + abs m' xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m) return xs'
con lo que la propiedad que hay que comprobar con QuickCheck es
teorema_de_existencia_de_divisores :: Property teorema_de_existencia_de_divisores = forAll mayoritario (not . null . divisoresMultiplos)
Soluciones
import Data.List (genericLength) import Test.QuickCheck divisoresMultiplos :: [Integer] -> [(Integer,Integer)] divisoresMultiplos xs = [(x,y) | x <- xs , y <- xs , y /= x , y `mod` x == 0] esMayoritario :: [Integer] -> Bool esMayoritario xs = not (null xs) && length xs > ceiling (n / 2) where n = fromIntegral (maximum xs) -- Comprobación del teorema -- ======================== -- La propiedad es teorema_de_existencia_de_divisores :: Property teorema_de_existencia_de_divisores = forAll mayoritario (not . null . divisoresMultiplos) -- mayoritario es un generador de conjuntos mayoritarios. Por ejemplo, -- λ> sample mayoritario -- [1,2] -- [2,5,7,8] -- [1,2,8,10,14] -- [3,8,11,12,13,15,18,19,22,23,25,26] -- [1,3,4,6] -- [3,6,9,11,12,14,17,19] mayoritario :: Gen [Integer] mayoritario = do m' <- arbitrary let m = 1 + abs m' xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m) return xs' -- La comprobación es -- λ> quickCheck teorema_de_existencia_de_divisores -- +++ OK, passed 100 tests.