{"id":99,"date":"2007-06-06T08:41:33","date_gmt":"2007-06-06T07:41:33","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=99"},"modified":"2007-06-08T13:55:57","modified_gmt":"2007-06-08T12:55:57","slug":"nie-sami-swoi","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2007\/06\/06\/nie-sami-swoi\/","title":{"rendered":"Nie sami swoi"},"content":{"rendered":"

Ile co najmniej przypadkowo wybranych os\u00f3b musi liczy\u0107 grupa, aby zawsze by\u0142o w niej albo dwoje znajomych, albo dwoje nieznajomych?
\nTrywialne zadanie. Dodajmy wi\u0119c trzy osoby.<\/p>\n

Ile co najmniej przypadkowo wybranych os\u00f3b musi liczy\u0107 grupa, aby zawsze by\u0142o w niej albo pi\u0119cioro znajomych, albo pi\u0119cioro obcych sobie ludzi?
\nPrzyby\u0142o tylko troje, a powsta\u0142 orzech nie tylko twardy, ale wr\u0119cz niemo\u017cliwy do zgryzienia, przynajmniej dotychczas. To zadanie wiele lat temu skomentowa\u0142 r\u00f3wnie genialny, co ekstrawagancki matematyk w\u0119gierski Paul Erd\u00f6s historyjk\u0105 science-fiction.<\/p>\n

Za\u0142\u00f3\u017cmy, \u017ce przybysze z kosmosu gro\u017c\u0105 zniszczeniem Ziemi, je\u015bli w ci\u0105gu roku uczeni nie wyznacz\u0105 warto\u015bci R(5,5) [<\/em>to matematyczny zapis powy\u017cszego „orzecha”]. Anga\u017cuj\u0105c wszystkie najt\u0119\u017csze umys\u0142y i najszybsze komputery mieliby\u015bmy szans\u0119 na ocalenie. Gdyby jednak gro\u017aba agresor\u00f3w wi\u0105za\u0142a si\u0119 z \u017c\u0105daniem znalezienia R(6,6) [<\/em>to superorzech], jedynym s\u0142usznym posuni\u0119ciem by\u0142by natychmiastowy kontratak wyprzedzaj\u0105cy<\/em>.<\/p>\n

\u0141atwo si\u0119 domy\u015bli\u0107, \u017ce w superorzechu chodzi o najmniejsz\u0105 grup\u0119 z sz\u00f3stk\u0105 obcych lub znajomych. Sens historyjki do dzi\u015b jest aktualny.<\/p>\n

Je\u015bli w trywialnym zadaniu wst\u0119pnym dodamy jedn\u0105 osob\u0119, to powstanie klasyczna \u0142amig\u0142\u00f3wka, znana jako „party problem”: ile co najmniej os\u00f3b powinno zjawi\u0107 si\u0119 na przyj\u0119ciu, aby w\u015br\u00f3d nich by\u0142o na pewno albo troje znajomych, albo troje nieznajomych?
\nGwoli jasno\u015bci przyk\u0142ad: cztery osoby nie wystarcz\u0105, bo je\u015bli przyjd\u0105 tylko dwa nie znaj\u0105ce si\u0119 ma\u0142\u017ce\u0144stwa, to \u017caden z dw\u00f3ch alternatywnych warunk\u00f3w nie b\u0119dzie spe\u0142niony.<\/p>\n

Dodanie jeszcze jednej osoby, ale „po\u0142owicznie”, czyli tylko do jednego z dwu warunk\u00f3w, sprawia, \u017ce ju\u017c powstaje orzech, cho\u0107 do rozgryzienia. Brzmi on nieco dziwnie: jaka jest najmniejsza grupa os\u00f3b z trojgiem znajomych lub czw\u00f3rk\u0105 obcych (albo z trzema nieznajomymi lub czterema znajomymi)? Napisa\u0142em „dziwnie”, bo czw\u00f3rk\u0119 tworz\u0105 cztery tr\u00f3jki (je\u015bli znaj\u0105 si\u0119 cztery osoby, to znaj\u0105 si\u0119 tak\u017ce ka\u017cde trzy z tych czterech), zatem tr\u00f3jka pojawi si\u0119 zawsze. Ot\u00f3\u017c chodzi o to, \u017ce – przechodz\u0105c do konkret\u00f3w – gdy zaprosimy na przyj\u0119cie osiem os\u00f3b, to brak tr\u00f3jki znajomych nie „wymusi” pojawienia si\u0119 czw\u00f3rki nieznajomych, natomiast gdy przyb\u0119dzie dziewi\u0119\u0107 os\u00f3b i nie b\u0119dzie w\u015br\u00f3d nich tr\u00f3jki znajomych, to czw\u00f3rka nieznajomych nieuchronnie si\u0119 pojawi.<\/p>\n

Kto zetkn\u0105\u0142 si\u0119 wcze\u015bniej z takimi \u0142amig\u0142\u00f3wkami, ten zapewne wie, \u017ce maj\u0105 one powa\u017cne i praktyczne konotacje – wi\u0105\u017c\u0105 si\u0119 z teori\u0105 graf\u00f3w, kt\u00f3ra bardzo si\u0119 przydaje w opl\u0105tanym sieci\u0105 sieci \u015bwiecie.<\/p>\n

Grupa znajomych i\/lub nieznajomych to graf pe\u0142ny, czyli zbi\u00f3r punkt\u00f3w (wierzcho\u0142k\u00f3w), z kt\u00f3rych ka\u017cde dwa po\u0142\u0105czone s\u0105 lini\u0105 (kraw\u0119dzi\u0105), za\u015b liczebno\u015b\u0107 najmniejszej grupy, czyli rozwi\u0105zanie ka\u017cdego z powy\u017cszych orzech\u00f3w, to tzw. liczba Ramseya – np. dla powy\u017cszego „dziwnego” orzecha wynosi ona dziewi\u0119\u0107, co zapisujemy: R(3,4) = 9.
\nNa rysunkach znajduj\u0105 si\u0119 przyk\u0142ady graf\u00f3w odpowiadaj\u0105cych trzem znajomym (zielone linie oznaczaj\u0105 znajomo\u015bci mi\u0119dzy osobami-punktami), czterem nieznajomym (czerwona linia to obco\u015b\u0107) oraz przyk\u0142adowemu rozwi\u0105zaniu „dziwnego” orzecha bez jakiegokolwiek tercetu obcych, za to z tercetami znajomych tworz\u0105cymi kwartet – i to niejeden.
\nPrzy okazji test spostrzegawczo\u015bci: prosz\u0119 ustali\u0107, ile w tym rozwi\u0105zaniu jest zielonych tr\u00f3jk\u0105t\u00f3w oraz czworok\u0105t\u00f3w z przek\u0105tnymi.<\/p>\n

\"klik.jpg\"<\/p>\n

Warto\u015bci R(3,4) = 9 oraz R(4,4) = 18 znaleziono przed ponad p\u00f3\u0142wieczem. W roku 1993 w prasie ameryka\u0144skiej pojawi\u0142a si\u0119 informacja o rozwi\u0105zaniu przez dw\u00f3ch uczonych, po trzech latach pracy z wykorzystaniem 110 komputer\u00f3w, donios\u0142ego problemu: ile os\u00f3b trzeba zaprosi\u0107 na party, aby by\u0142y w\u015br\u00f3d nich przynajmniej cztery znaj\u0105ce si\u0119 albo pi\u0119\u0107 obcych sobie? Odpowied\u017a (25) dotyczy\u0142a oczywi\u015bcie warto\u015bci R(4,5), ale po „biesiadnym” przedstawieniu zagadnienia nie brakowa\u0142o komentarzy o marnowaniu czasu i pieni\u0119dzy na nikomu nie potrzebne badania, zamiast przekazania ich dla g\u0142odnych dzieci. Kr\u00f3tko m\u00f3wi\u0105c, dosta\u0142o si\u0119 matematykom darmozjadom – polskiemu profesorowi z Rochester Institute of Technology Stanis\u0142awowi Radziszowskiemu i jego wsp\u00f3\u0142pracownikowi z Australii Brendonowi McKay.<\/p>\n

Na koniec prosta \u0142amig\u0142\u00f3wka bez protekcji, czyli znajomo\u015bci nie maj\u0105 znaczenia.<\/p>\n

Nazwijmy grup\u0119 jednorodn\u0105, je\u015bli w tej grupie albo ka\u017cdy zna ka\u017cdego, albo nikt nie zna nikogo.
\nIle co najmniej os\u00f3b musi uczestniczy\u0107 w przyj\u0119ciu, aby\u015bmy mogli stwierdzi\u0107 z ca\u0142\u0105 pewno\u015bci\u0105, \u017ce s\u0105 w\u015br\u00f3d nich dwie trzyosobowe grupy jednorodne, przy czym nikt z jednej grupy nie wchodzi w sk\u0142ad drugiej grupy?<\/p>\n","protected":false},"excerpt":{"rendered":"

Ile co najmniej przypadkowo wybranych os\u00f3b musi liczy\u0107 grupa, aby zawsze by\u0142o w niej albo dwoje znajomych, albo dwoje nieznajomych? Trywialne zadanie. Dodajmy wi\u0119c trzy osoby. Ile co najmniej przypadkowo wybranych os\u00f3b musi liczy\u0107 grupa, aby zawsze by\u0142o w niej albo pi\u0119cioro znajomych, albo pi\u0119cioro obcych sobie ludzi? Przyby\u0142o tylko troje, a powsta\u0142 orzech nie […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/99"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=99"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/99\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=99"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=99"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=99"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}