{"id":5373,"date":"2020-01-17T05:30:33","date_gmt":"2020-01-17T03:30:33","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5373"},"modified":"2020-01-24T07:42:13","modified_gmt":"2020-01-24T05:42:13","slug":"teorema-de-la-amistad","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/teorema-de-la-amistad\/","title":{"rendered":"Teorema de la amistad"},"content":{"rendered":"<p>El <strong>teorema de la amistad<\/strong> afirma que<\/p>\n<blockquote><p>\nEn cualquier reuni\u00f3n de n personas hay al menos dos personas que tienen el mismo n\u00famero de amigos (suponiendo que la relaci\u00f3n de amistad es sim\u00e9trica).\n<\/p><\/blockquote>\n<p>Se pueden usar las siguientes representaciones:<\/p>\n<ul>\n<li>n\u00fameros enteros para representar a las personas,<\/li>\n<li>pares de enteros (x,y), con x &lt; y, para representar que la persona x e y son amigas y<\/li>\n<li>lista de pares de enteros para representar la reuni\u00f3n junto con las relaciones de amistad.<\/li>\n<\/ul>\n<p>Por ejemplo, [(2,3),(3,5)] representa una reuni\u00f3n de tres personas<br \/>\n(2, 3 y 5) donde<\/p>\n<ul>\n<li>2 es amiga de 3,<\/li>\n<li>3 es amiga de 2 y 5 y<\/li>\n<li>5 es amiga de 3.<br \/>\nSi clasificamos las personas poniendo en la misma clase las que tienen el mismo n\u00famero de amigos, se obtiene [[2,5],[3]] ya que 2 y 5 tienen 1 amigo y 3 tiene 2 amigos.<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   clasesAmigos :: [(Int,Int)] -> [[Int]]\n<\/pre>\n<p>tal que (clasesAmigos r) es la clasificaci\u00f3n seg\u00fan el n\u00famero de amigos de las personas de la reuni\u00f3n r; es decir, la lista cuyos elementos son las listas de personas con 1 amigo, con 2 amigos y as\u00ed hasta que se completa todas las personas de la reuni\u00f3n r. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   clasesAmigos [(2,3),(3,5)]            ==  [[2,5],[3]]\n   clasesAmigos [(2,3),(4,5)]            ==  [[2,3,4,5]]\n   clasesAmigos [(2,3),(2,5),(3,5)]      ==  [[2,3,5]]\n   clasesAmigos [(2,3),(3,4),(2,5)]      ==  [[4,5],[2,3]]\n   clasesAmigos [(x,x+1) | x <- [1..5]]  ==  [[1,6],[2,3,4,5]]\n   length (clasesAmigos [(x,x+1) | x <- [1..2020]]) == 2\n<\/pre>\n<p>Comprobar con QuickCheck el teorema de la amistad; es decir, si r es una lista de pares de enteros, entonces (clasesAmigos r') donde r' es la lista de los pares (x,y) de r con x &lt; y y se supone que r' es no vac\u00eda.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (nub, sort)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nclasesAmigos :: [(Int,Int)] -> [[Int]]\nclasesAmigos ps =\n  filter (not . null)\n         [[x | x <- xs, numeroDeAmigos ps x == n] | n <- [1..length xs]] \n  where xs = personas ps\n    \n-- (personas ps) es la lista de personas en la reuni\u00f3n ps. Por ejemplo,\n--    personas [(2,3),(3,5)]  ==  [2,3,5]\npersonas :: [(Int,Int)] -> [Int]\npersonas ps = sort (nub (map fst ps ++ map snd ps))\n\n-- (numeroDeAmigos ps x) es el n\u00famero de amigos de x en la reuni\u00f3n\n-- ps. Por ejemplo, \n--    numeroDeAmigos [(2,3),(3,5)] 2  ==  1\n--    numeroDeAmigos [(2,3),(3,5)] 3  ==  2\n--    numeroDeAmigos [(2,3),(3,5)] 5  ==  1\nnumeroDeAmigos :: [(Int,Int)] -> Int -> Int\nnumeroDeAmigos ps x = length (amigos ps x)\n\n-- (amigos ps x) es la lista de los amigos de x en la reuni\u00f3n ps. Por\n-- ejemplo, \n--    amigos [(2,3),(3,5)] 2  ==  [3]\n--    amigos [(2,3),(3,5)] 3  ==  [5,2]\n--    amigos [(2,3),(3,5)] 5  ==  [3]\namigos :: [(Int,Int)] -> Int -> [Int]\namigos ps x =\n  nub ([b | (a,b) <- ps, a == x] ++ [a | (a,b) <- ps, b == x])\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nclasesAmigos2 :: [(Int,Int)] -> [[Int]]\nclasesAmigos2 = clases . sort . tablaAmigos\n  where\n    clases [] = []\n    clases ps@((x,y):ps') = (map snd (takeWhile (\\(a,b) -> a == x) ps)) :\n                            clases (dropWhile (\\(a,b) -> a == x) ps')\n\n-- (tablaAmigos ps) es la lista de pares (a,b) tales que b es una\n-- persona de la reuni\u00f3n ps y a es su n\u00famero de amigos. Por ejemplo,\n--    tablaAmigos [(2,3),(3,5)]   ==  [(1,2),(2,3),(1,5)]\ntablaAmigos :: [(Int,Int)] -> [(Int,Int)]\ntablaAmigos ps = [(numeroDeAmigos ps x,x) | x <- personas ps]\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_equivalencia :: [(Int,Int)] -> Property\nprop_equivalencia ps =\n  not (null ps')\n  ==> \n  clasesAmigos ps' == clasesAmigos2 ps'\n  where ps' = [(x,y) | (x,y) <- ps, x < y]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_equivalencia\n--    +++ OK, passed 100 tests.\n--    (1.06 secs, 337,106,752 bytes)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> length (clasesAmigos [(x,x+1) | x <- [1..200]]) \n--    2\n--    (2.37 secs, 804,402,848 bytes)\n--    \u03bb> length (clasesAmigos2 [(x,x+1) | x <- [1..200]]) \n--    2\n--    (0.02 secs, 4,287,256 bytes)\n\n-- El teorema de la amistad\n-- ========================\n\n-- La propiedad es\nteoremaDeLaAmistad :: [(Int,Int)] -> Property\nteoremaDeLaAmistad ps =\n  not (null ps')\n  ==> \n  not (null [xs | xs <- clasesAmigos2 ps', length xs > 1])\n  where ps' = [(x,y) | (x,y) <- ps, x < y]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck teoremaDeLaAmistad\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Referencia<\/h4>\n<ul>\n<li><a href=\"http:\/\/bit.ly\/2rMXtBc\">Pigeonhole among friends<\/a><\/li>\n<\/ul>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nMe dijo el agua clara que re\u00eda,<br \/>\nbajo el sol, sobre el m\u00e1rmol de la fuente:<br \/>\nsi te inquieta el enigma del presente<br \/>\naprende el son de la salmodia m\u00eda.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>El teorema de la amistad afirma que En cualquier reuni\u00f3n de n personas hay al menos dos personas que tienen el mismo n\u00famero de amigos (suponiendo que la relaci\u00f3n de amistad es sim\u00e9trica). Se pueden usar las siguientes representaciones: n\u00fameros enteros para representar a las personas, pares de enteros (x,y), con x &lt; y, para&#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":[8,59,38,80,28,10,181,24,141,11,16,14,34,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5373"}],"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=5373"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5373\/revisions"}],"predecessor-version":[{"id":5435,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5373\/revisions\/5435"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5373"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5373"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5373"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}