{"id":726,"date":"2012-01-27T21:10:08","date_gmt":"2012-01-27T21:10:08","guid":{"rendered":"http:\/\/41j.com\/blog\/?p=726"},"modified":"2012-01-27T21:23:28","modified_gmt":"2012-01-27T21:23:28","slug":"six-people-at-a-party","status":"publish","type":"post","link":"https:\/\/41j.com\/blog\/2012\/01\/six-people-at-a-party\/","title":{"rendered":"Six People at a Party"},"content":{"rendered":"<p>When there are six people at a party there will always be either:<\/p>\n<p>1. At least three people who all know each other.<br \/>\n2. At least three people, none of whom know each other.<\/p>\n<p>One of the above statements must be true. You can&#8217;t have a party of six people where everybody knows one other person but there&#8217;s no group of three people none of whom know each other, for example.<\/p>\n<p>This can be shown using graph theory.<\/p>\n<p>1. We represent the group of six people with a graph.<br \/>\n2. Edges between vertices are of two types (know or don&#8217;t know).<br \/>\n3. Pick a vertex at random. Any vertex will have at least 3 edges of one type. For example:<\/p>\n<p><a href=\"http:\/\/41j.com\/blog\/wp-content\/uploads\/2012\/01\/6people.png\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/41j.com\/blog\/wp-content\/uploads\/2012\/01\/6people-300x144.png\" alt=\"\" title=\"6people\" width=\"300\" height=\"144\" class=\"aligncenter size-medium wp-image-727\" srcset=\"https:\/\/41j.com\/blog\/wp-content\/uploads\/2012\/01\/6people-300x144.png 300w, https:\/\/41j.com\/blog\/wp-content\/uploads\/2012\/01\/6people.png 602w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p>Where known\/not known is represented by solid\/dotted.<\/p>\n<p>4. Now, either one of the edges bc, bd or cd is solid or not.<\/p>\n<p>5. If one edge is solid, 3 people all know\/don&#8217;t know each other (abc,acd, or abd).<\/p>\n<p>6. If none of the edges exists then bcd know\/don&#8217;t know each other.<\/p>\n<h2>Notes<\/h2>\n<p>The dot file used to generate the graph above:<\/p>\n<pre class=\"brush: plain; title: ; notranslate\" title=\"\">\r\ngraph graphname {\r\n  a &#x5B;shape=circle];\r\n  b &#x5B;shape=circle];\r\n  c &#x5B;shape=circle];\r\n  d &#x5B;shape=circle]; \r\n  e &#x5B;shape=circle];\r\n  f &#x5B;shape=circle];\r\n\r\n\r\n  a -- b;\r\n  a -- c;\r\n  a -- d;\r\n  a -- e &#x5B;style=dotted];\r\n  a -- f &#x5B;style=dotted];\r\n}\r\n<\/pre>\n<p>I encountered this problem in &#8220;Introduction to Graph Theory&#8221; by Robin J. Wilson (great book).<\/p>\n<p>You can read more about the problem and it&#8217;s generalisation on wikipedia <a href=\"http:\/\/en.wikipedia.org\/wiki\/Theorem_on_friends_and_strangers\">here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>When there are six people at a party there will always be either: 1. At least three people who all know each other. 2. At least three people, none of whom know each other. One of the above statements must be true. You can&#8217;t have a party of six people where everybody knows one other [&hellip;]<\/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,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-726","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-bI","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/726","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=726"}],"version-history":[{"count":4,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/726\/revisions"}],"predecessor-version":[{"id":731,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/726\/revisions\/731"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=726"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=726"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=726"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}