{"id":5812,"date":"2020-04-24T05:30:50","date_gmt":"2020-04-24T03:30:50","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5812"},"modified":"2020-05-01T08:22:39","modified_gmt":"2020-05-01T06:22:39","slug":"conjetura-de-las-familias-estables-por-uniones","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/conjetura-de-las-familias-estables-por-uniones\/","title":{"rendered":"Conjetura de las familias estables por uniones"},"content":{"rendered":"<p>La <a href=\"http:\/\/bit.ly\/2IbBGc7\">conjetura de las familias estables por uniones<\/a> fue planteada por P\u00e9ter Frankl en 1979 y a\u00fan sigue abierta.<\/p>\n<p>Una familia de conjuntos es estable por uniones si la uni\u00f3n de dos conjuntos cualesquiera de la familia pertenece a la familia. Por ejemplo, {\u2205, {1}, {2}, {1,2}, {1,3}, {1,2,3}} es estable por uniones; pero {{1}, {2}, {1,3}, {1,2,3}} no lo es.<\/p>\n<p>La conjetura afirma que toda familia no vac\u00eda estable por uniones y distinta de {\u2205} posee alg\u00fan elemento que pertenece al menos a la mitad de los conjuntos de la familia.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\"> \n   esEstable :: Ord a => Set (Set a) -> Bool\n   familiasEstables :: Ord a => Set a -> Set (Set (Set a))\n   mayoritarios :: Ord a => Set (Set a) -> [a]\n   conjeturaFrankl :: Int -> Bool\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(esEstable f) se verifica si la familia f es estable por uniones. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">   \n     \u03bb> esEstable (fromList [empty, fromList [1,2], fromList [1..5]])\n     True\n     \u03bb> esEstable (fromList [empty, fromList [1,7], fromList [1..5]])\n     False\n     \u03bb> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]])\n     True\n<\/pre>\n<ul>\n<li>(familiasEstables c) es el conjunto de las familias estables por uniones formadas por elementos del conjunto c. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">   \n     \u03bb> familiasEstables (fromList [1..2])\n     fromList\n       [ fromList []\n       , fromList [fromList []]\n       , fromList [fromList [],fromList [1]]\n       , fromList [fromList [],fromList [1],fromList [1,2]],\n         fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]\n       , fromList [fromList [],fromList [1,2]]\n       , fromList [fromList [],fromList [1,2],fromList [2]]\n       , fromList [fromList [],fromList [2]]\n       , fromList [fromList [1]]\n       , fromList [fromList [1],fromList [1,2]]\n       , fromList [fromList [1],fromList [1,2],fromList [2]]\n       , fromList [fromList [1,2]]\n       , fromList [fromList [1,2],fromList [2]]\n       , fromList [fromList [2]]]\n     \u03bb> size (familiasEstables (fromList [1,2]))\n     14\n     \u03bb> size (familiasEstables (fromList [1..3]))\n     122\n     \u03bb> size (familiasEstables (fromList [1..4]))\n     4960\n<\/pre>\n<ul>\n<li>(mayoritarios f) es la lista de elementos que pertenecen al menos a la mitad de los conjuntos de la familia f. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">   \n     mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3]\n     mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == []\n<\/pre>\n<ul>\n<li>(conjeturaFrankl n) se verifica si para toda familia f formada por elementos del conjunto {1,2,&#8230;,n} no vac\u00eda, estable por uniones y  distinta de {\u2205} posee alg\u00fan elemento que pertenece al menos a la mitad de los conjuntos de f. Por ejemplo.<\/li>\n<\/ul>\n<pre lang=\"text\">   \n     conjeturaFrankl 2  ==  True\n     conjeturaFrankl 3  ==  True\n     conjeturaFrankl 4  ==  True\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n\nimport Data.Set  as S ( Set\n                      , delete\n                      , deleteFindMin\n                      , empty\n                      , filter\n                      , fromList\n                      , insert\n                      , map\n                      , member\n                      , null\n                      , singleton\n                      , size\n                      , toList\n                      , union\n                      , unions\n                      )\nimport Data.List as L ( filter\n                      , null\n                      )\n\nesEstable :: Ord a => Set (Set a) -> Bool\nesEstable xss =\n  and [ys `S.union` zs `member` xss | (ys,yss) <- selecciones xss\n                                    , zs <- toList yss]\n\n-- (seleccciones xs) es la lista de los pares formada por un elemento de\n-- xs y los restantes elementos. Por ejemplo,\n--    \u03bb> selecciones (fromList [3,2,5])\n--    [(2,fromList [3,5]),(3,fromList [2,5]),(5,fromList [2,3])]\nselecciones :: Ord a => Set a -> [(a,Set a)]\nselecciones xs =\n  [(x,delete x xs) | x <- toList xs] \n\nfamiliasEstables :: Ord a => Set a -> Set (Set (Set a))\nfamiliasEstables xss =\n  S.filter esEstable (familias xss)\n\n-- (familias c) es la familia formadas con elementos de c. Por ejemplo,\n--    \u03bb> mapM_ print (familias (fromList [1,2]))\n--    fromList []\n--    fromList [fromList []]\n--    fromList [fromList [],fromList [1]]\n--    fromList [fromList [],fromList [1],fromList [1,2]]\n--    fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]\n--    fromList [fromList [],fromList [1],fromList [2]]\n--    fromList [fromList [],fromList [1,2]]\n--    fromList [fromList [],fromList [1,2],fromList [2]]\n--    fromList [fromList [],fromList [2]]\n--    fromList [fromList [1]]\n--    fromList [fromList [1],fromList [1,2]]\n--    fromList [fromList [1],fromList [1,2],fromList [2]]\n--    fromList [fromList [1],fromList [2]]\n--    fromList [fromList [1,2]]\n--    fromList [fromList [1,2],fromList [2]]\n--    fromList [fromList [2]]\n--    \u03bb> size (familias (fromList [1,2]))\n--    16\n--    \u03bb> size (familias (fromList [1,2,3]))\n--    256\n--    \u03bb> size (familias (fromList [1,2,3,4]))\n--    65536\nfamilias :: Ord a => Set a -> Set (Set (Set a))\nfamilias c =\n  subconjuntos (subconjuntos c)\n\n-- (subconjuntos c) es el conjunto de los subconjuntos de c. Por ejemplo,\n--    \u03bb> mapM_ print (subconjuntos (fromList [1,2,3]))\n--    fromList []\n--    fromList [1]\n--    fromList [1,2]\n--    fromList [1,2,3]\n--    fromList [1,3]\n--    fromList [2]\n--    fromList [2,3]\n--    fromList [3]\nsubconjuntos :: Ord a => Set a -> Set (Set a)\nsubconjuntos c\n  | S.null c  = singleton empty\n  | otherwise = S.map (insert x) sr `union` sr\n  where (x,rc) = deleteFindMin c\n        sr     = subconjuntos rc\n\n-- (elementosFamilia f) es el conjunto de los elementos de los elementos\n-- de la familia f. Por ejemplo, \n--    \u03bb> elementosFamilia (fromList [empty, fromList [1,2], fromList [2,5]])\n--    fromList [1,2,5]\nelementosFamilia :: Ord a => Set (Set a) -> Set a\nelementosFamilia = unions . toList\n\n-- (nOcurrencias f x) es el n\u00famero de conjuntos de la familia f a los\n-- que pertenece el elemento x. Por ejemplo,\n--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 3 == 2\n--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 4 == 0\n--    nOcurrencias (fromList [empty, fromList [1,3], fromList [3,5]]) 5 == 1\nnOcurrencias :: Ord a => Set (Set a) -> a -> Int\nnOcurrencias f x =\n  length (L.filter (x `member`) (toList f))\n\nmayoritarios :: Ord a => Set (Set a) -> [a]\nmayoritarios f =\n  [x | x <- toList (elementosFamilia f)\n     , nOcurrencias f x >= n]\n  where n = (1 + size f) `div` 2\n\nconjeturaFrankl :: Int -> Bool\nconjeturaFrankl n =\n  and [ not (L.null (mayoritarios f))\n      | f <- fs\n      , f \/= fromList []\n      , f \/= fromList [empty]]\n  where fs = toList (familiasEstables (fromList [1..n]))\n\n\n-- conjeturaFrankl' :: Int -> Bool\nconjeturaFrankl' n =\n  [f | f <- fs\n     , L.null (mayoritarios f)\n     , f \/= fromList []\n     , f \/= fromList [empty]]\n  where fs = toList (familiasEstables (fromList [1..n]))\n<\/pre>\n<h4>Otras soluciones<\/h4>\n<ul>\n<li>Se pueden escribir otras soluciones en los comentarios.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>La conjetura de las familias estables por uniones fue planteada por P\u00e9ter Frankl en 1979 y a\u00fan sigue abierta. Una familia de conjuntos es estable por uniones si la uni\u00f3n de dos conjuntos cualesquiera de la familia pertenece a la familia. Por ejemplo, {\u2205, {1}, {2}, {1,2}, {1,3}, {1,2,3}} es estable por uniones; pero {{1},&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[7],"tags":[100,8,25,475,30,291,38,261,459,28,473,141,472,474,477,260,242,476],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5812"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=5812"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5812\/revisions"}],"predecessor-version":[{"id":5844,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5812\/revisions\/5844"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5812"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5812"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5812"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}