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
|
1 2 |
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,
|
1 2 3 |
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,
|
1 2 |
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
|
1 2 3 4 5 6 |
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
|
1 2 3 |
teorema_de_existencia_de_divisores :: Property teorema_de_existencia_de_divisores = forAll mayoritario (not . null . divisoresMultiplos) |
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 |
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. |
Pensamiento
Guiomar, Guiomar,
mírame en ti castigado:
reo de haberte creado,
ya no te puedo olvidar.Antonio Machado