Nie sami swoi

Ile co najmniej przypadkowo wybranych osób musi liczyć grupa, aby zawsze było w niej albo dwoje znajomych, albo dwoje nieznajomych?
Trywialne zadanie. Dodajmy więc trzy osoby.

Ile co najmniej przypadkowo wybranych osób musi liczyć grupa, aby zawsze było w niej albo pięcioro znajomych, albo pięcioro obcych sobie ludzi?
Przybyło tylko troje, a powstał orzech nie tylko twardy, ale wręcz niemożliwy do zgryzienia, przynajmniej dotychczas. To zadanie wiele lat temu skomentował równie genialny, co ekstrawagancki matematyk węgierski Paul Erdös historyjką science-fiction.

Załóżmy, że przybysze z kosmosu grożą zniszczeniem Ziemi, jeśli w ciągu roku uczeni nie wyznaczą wartości R(5,5) [to matematyczny zapis powyższego „orzecha”]. Angażując wszystkie najtęższe umysły i najszybsze komputery mielibyśmy szansę na ocalenie. Gdyby jednak groźba agresorów wiązała się z żądaniem znalezienia R(6,6) [to superorzech], jedynym słusznym posunięciem byłby natychmiastowy kontratak wyprzedzający.

Łatwo się domyślić, że w superorzechu chodzi o najmniejszą grupę z szóstką obcych lub znajomych. Sens historyjki do dziś jest aktualny.

Jeśli w trywialnym zadaniu wstępnym dodamy jedną osobę, to powstanie klasyczna łamigłówka, znana jako „party problem”: ile co najmniej osób powinno zjawić się na przyjęciu, aby wśród nich było na pewno albo troje znajomych, albo troje nieznajomych?
Gwoli jasności przykład: cztery osoby nie wystarczą, bo jeśli przyjdą tylko dwa nie znające się małżeństwa, to żaden z dwóch alternatywnych warunków nie będzie spełniony.

Dodanie jeszcze jednej osoby, ale „połowicznie”, czyli tylko do jednego z dwu warunków, sprawia, że już powstaje orzech, choć do rozgryzienia. Brzmi on nieco dziwnie: jaka jest najmniejsza grupa osób z trojgiem znajomych lub czwórką obcych (albo z trzema nieznajomymi lub czterema znajomymi)? Napisałem „dziwnie”, bo czwórkę tworzą cztery trójki (jeśli znają się cztery osoby, to znają się także każde trzy z tych czterech), zatem trójka pojawi się zawsze. Otóż chodzi o to, że – przechodząc do konkretów – gdy zaprosimy na przyjęcie osiem osób, to brak trójki znajomych nie „wymusi” pojawienia się czwórki nieznajomych, natomiast gdy przybędzie dziewięć osób i nie będzie wśród nich trójki znajomych, to czwórka nieznajomych nieuchronnie się pojawi.

Kto zetknął się wcześniej z takimi łamigłówkami, ten zapewne wie, że mają one poważne i praktyczne konotacje – wiążą się z teorią grafów, która bardzo się przydaje w oplątanym siecią sieci świecie.

Grupa znajomych i/lub nieznajomych to graf pełny, czyli zbiór punktów (wierzchołków), z których każde dwa połączone są linią (krawędzią), zaś liczebność najmniejszej grupy, czyli rozwiązanie każdego z powyższych orzechów, to tzw. liczba Ramseya – np. dla powyższego „dziwnego” orzecha wynosi ona dziewięć, co zapisujemy: R(3,4) = 9.
Na rysunkach znajdują się przykłady grafów odpowiadających trzem znajomym (zielone linie oznaczają znajomości między osobami-punktami), czterem nieznajomym (czerwona linia to obcość) oraz przykładowemu rozwiązaniu „dziwnego” orzecha bez jakiegokolwiek tercetu obcych, za to z tercetami znajomych tworzącymi kwartet – i to niejeden.
Przy okazji test spostrzegawczości: proszę ustalić, ile w tym rozwiązaniu jest zielonych trójkątów oraz czworokątów z przekątnymi.

klik.jpg

Wartości R(3,4) = 9 oraz R(4,4) = 18 znaleziono przed ponad półwieczem. W roku 1993 w prasie amerykańskiej pojawiła się informacja o rozwiązaniu przez dwóch uczonych, po trzech latach pracy z wykorzystaniem 110 komputerów, doniosłego problemu: ile osób trzeba zaprosić na party, aby były wśród nich przynajmniej cztery znające się albo pięć obcych sobie? Odpowiedź (25) dotyczyła oczywiście wartości R(4,5), ale po „biesiadnym” przedstawieniu zagadnienia nie brakowało komentarzy o marnowaniu czasu i pieniędzy na nikomu nie potrzebne badania, zamiast przekazania ich dla głodnych dzieci. Krótko mówiąc, dostało się matematykom darmozjadom – polskiemu profesorowi z Rochester Institute of Technology Stanisławowi Radziszowskiemu i jego współpracownikowi z Australii Brendonowi McKay.

Na koniec prosta łamigłówka bez protekcji, czyli znajomości nie mają znaczenia.

Nazwijmy grupę jednorodną, jeśli w tej grupie albo każdy zna każdego, albo nikt nie zna nikogo.
Ile co najmniej osób musi uczestniczyć w przyjęciu, abyśmy mogli stwierdzić z całą pewnością, że są wśród nich dwie trzyosobowe grupy jednorodne, przy czym nikt z jednej grupy nie wchodzi w skład drugiej grupy?