Conjetura de las familias estables por uniones
La conjetura de las familias estables por uniones fue planteada por Péter Frankl en 1979 y aún sigue abierta.
Una familia de conjuntos es estable por uniones si la unión de dos conjuntos cualesquiera de la familia pertenece a la familia. Por ejemplo, {∅, {1}, {2}, {1,2}, {1,3}, {1,2,3}} es estable por uniones; pero {{1}, {2}, {1,3}, {1,2,3}} no lo es.
La conjetura afirma que toda familia no vacía estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de la familia.
Definir las funciones
|
1 2 3 4 |
esEstable :: Ord a => Set (Set a) -> Bool familiasEstables :: Ord a => Set a -> Set (Set (Set a)) mayoritarios :: Ord a => Set (Set a) -> [a] conjeturaFrankl :: Int -> Bool |
tales que
- (esEstable f) se verifica si la familia f es estable por uniones. Por ejemplo,
|
1 2 3 4 5 6 |
λ> esEstable (fromList [empty, fromList [1,2], fromList [1..5]]) True λ> esEstable (fromList [empty, fromList [1,7], fromList [1..5]]) False λ> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]]) True |
- (familiasEstables c) es el conjunto de las familias estables por uniones formadas por elementos del conjunto c. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
λ> familiasEstables (fromList [1..2]) fromList [ fromList [] , fromList [fromList []] , fromList [fromList [],fromList [1]] , fromList [fromList [],fromList [1],fromList [1,2]], fromList [fromList [],fromList [1],fromList [1,2],fromList [2]] , fromList [fromList [],fromList [1,2]] , fromList [fromList [],fromList [1,2],fromList [2]] , fromList [fromList [],fromList [2]] , fromList [fromList [1]] , fromList [fromList [1],fromList [1,2]] , fromList [fromList [1],fromList [1,2],fromList [2]] , fromList [fromList [1,2]] , fromList [fromList [1,2],fromList [2]] , fromList [fromList [2]]] λ> size (familiasEstables (fromList [1,2])) 14 λ> size (familiasEstables (fromList [1..3])) 122 λ> size (familiasEstables (fromList [1..4])) 4960 |
- (mayoritarios f) es la lista de elementos que pertenecen al menos a la mitad de los conjuntos de la familia f. Por ejemplo,
|
1 2 |
mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3] mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == [] |
- (conjeturaFrankl n) se verifica si para toda familia f formada por elementos del conjunto {1,2,…,n} no vacía, estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de f. Por ejemplo.
|
1 2 3 |
conjeturaFrankl 2 == True conjeturaFrankl 3 == True conjeturaFrankl 4 == True |
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
import Data.Set as S ( Set , delete , deleteFindMin , empty , filter , fromList , insert , map , member , null , singleton , size , toList , union , unions ) import Data.List as L ( filter , null ) esEstable :: Ord a => Set (Set a) -> Bool esEstable xss = and [ys `S.union` zs `member` xss | (ys,yss) <- selecciones xss , zs <- toList yss] -- (seleccciones xs) es la lista de los pares formada por un elemento de -- xs y los restantes elementos. Por ejemplo, -- λ> selecciones (fromList [3,2,5]) -- [(2,fromList [3,5]),(3,fromList [2,5]),(5,fromList [2,3])] selecciones :: Ord a => Set a -> [(a,Set a)] selecciones xs = [(x,delete x xs) | x <- toList xs] familiasEstables :: Ord a => Set a -> Set (Set (Set a)) familiasEstables xss = S.filter esEstable (familias xss) -- (familias c) es la familia formadas con elementos de c. Por ejemplo, -- λ> mapM_ print (familias (fromList [1,2])) -- fromList [] -- fromList [fromList []] -- fromList [fromList [],fromList [1]] -- fromList [fromList [],fromList [1],fromList [1,2]] -- fromList [fromList [],fromList [1],fromList [1,2],fromList [2]] -- fromList [fromList [],fromList [1],fromList [2]] -- fromList [fromList [],fromList [1,2]] -- fromList [fromList [],fromList [1,2],fromList [2]] -- fromList [fromList [],fromList [2]] -- fromList [fromList [1]] -- fromList [fromList [1],fromList [1,2]] -- fromList [fromList [1],fromList [1,2],fromList [2]] -- fromList [fromList [1],fromList [2]] -- fromList [fromList [1,2]] -- fromList [fromList [1,2],fromList [2]] -- fromList [fromList [2]] -- λ> size (familias (fromList [1,2])) -- 16 -- λ> size (familias (fromList [1,2,3])) -- 256 -- λ> size (familias (fromList [1,2,3,4])) -- 65536 familias :: Ord a => Set a -> Set (Set (Set a)) familias c = subconjuntos (subconjuntos c) -- (subconjuntos c) es el conjunto de los subconjuntos de c. Por ejemplo, -- λ> mapM_ print (subconjuntos (fromList [1,2,3])) -- fromList [] -- fromList [1] -- fromList [1,2] -- fromList [1,2,3] -- fromList [1,3] -- fromList [2] -- fromList [2,3] -- fromList [3] subconjuntos :: Ord a => Set a -> Set (Set a) subconjuntos c | S.null c = singleton empty | otherwise = S.map (insert x) sr `union` sr where (x,rc) = deleteFindMin c sr = subconjuntos rc -- (elementosFamilia f) es el conjunto de los elementos de los elementos -- de la familia f. Por ejemplo, -- λ> elementosFamilia (fromList [empty, fromList [1,2], fromList [2,5]]) -- fromList [1,2,5] elementosFamilia :: Ord a => Set (Set a) -> Set a elementosFamilia = unions . toList -- (nOcurrencias f x) es el número de conjuntos de la familia f a los -- que pertenece el elemento x. Por ejemplo, -- nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 3 == 2 -- nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 4 == 0 -- nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 5 == 1 nOcurrencias :: Ord a => Set (Set a) -> a -> Int nOcurrencias f x = length (L.filter (x `member`) (toList f)) mayoritarios :: Ord a => Set (Set a) -> [a] mayoritarios f = [x | x <- toList (elementosFamilia f) , nOcurrencias f x >= n] where n = (1 + size f) `div` 2 conjeturaFrankl :: Int -> Bool conjeturaFrankl n = and [ not (L.null (mayoritarios f)) | f <- fs , f /= fromList [] , f /= fromList [empty]] where fs = toList (familiasEstables (fromList [1..n])) -- conjeturaFrankl' :: Int -> Bool conjeturaFrankl' n = [f | f <- fs , L.null (mayoritarios f) , f /= fromList [] , f /= fromList [empty]] where fs = toList (familiasEstables (fromList [1..n])) |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>