Największa liczba na świecie

Ludzie od niepamiętnych czasów prześcigali się w biciu rekordów w najprzeróżniejszych dziedzinach, od czysto sportowych (szybciej, wyżej, mocniej), poprzez cywilizacyjne (wyższe budowle, większe samoloty, szybsze komputery), aż po całkiem absurdalne, żeby nie powiedzieć głupie.

Taka już jest bowiem nasza natura, że jeśli tylko mamy szansę zrobienia czegoś w najlepszy z możliwych sposobów, to na pewno podejmiemy próbę zrobienia tego. Mania bicia rekordów nie ominęła również matematyków, którzy prześcigają się w znajdowaniu coraz większych liczb pierwszych czy też coraz dłuższych rozwinięć dziesiętnych liczby $\text{[math]}$ W artykule tym zaprezentujemy jeden z takich matematycznych rekordów. Przedstawimy największą liczbę, jaka kiedykolwiek została użyta w pracy matematycznej.

Aby dobrze zrozumieć, co wyraża największa liczba na świecie, konieczne będzie krótkie wprowadzenie, które zaczniemy od prostej obserwacji matematyczno-socjologicznej.

Sześć osób na przyjęciu

Wyobraźmy sobie, że w jakimś miejscu (np. na przyjęciu) spotyka się pewna grupa ludzi i, jak to w życiu zwykle bywa, niektórzy z nich znają się, inni zaś są sobie obcy. Możemy założyć, że relacja bycia znajomym jest określona dla każdej pary osób (albo się znają, albo nie znają) i jest symetryczna (jak ja znam ciebie, to i ty znasz mnie). Jeśli spojrzymy teraz na dowolną grupę złożoną z sześciu osób i przeanalizujemy układ znajomości między nimi, to łatwo dojdziemy do następującego spostrzeżenia:

Twierdzenie 1. Wśród dowolnych sześciu osób zawsze znajdziemy:

$\text{[math]}$: albo trzy osoby, które znają się wzajemnie (każda z każdą),
$\text{[math]}$: albo trzy osoby, które nie znają się wcale (żadna z żadną).

Dowód. Aby udowodnić ten fakt, przeformułujemy go na język teorii grafów następująco: każdą z sześciu osób utożsamiamy z innym wierzchołkiem grafu, a następnie każdą parę wierzchołków (osób) łączymy krawędzią. Powstanie w ten sposób graf, który nazywamy grafem pełnym (lub kliką) na sześciu wierzchołkach i oznaczamy przez $\text{[math]}$ . Układ znajomości przedstawiamy w ten sposób, że każdej krawędzi nadajemy jeden z dwóch kolorów: zielony – jeśli osoby umieszczone w wierzchołkach, które ona łączy, znają się, lub czarny – jeśli osoby te nie znają się. Wystarczy teraz pokazać, że przy dowolnym takim zielono-czarnym kolorowaniu krawędzi zawsze znajdziemy trzy wierzchołki połączone krawędziami w jednym kolorze (tworzące zieloną lub czarną klikę $\text{[math]}$ ).

Ustalmy w pokolorowanym już grafie dowolny wierzchołek $\text{[math]}$ i zauważmy, że skoro wychodzi z niego pięć krawędzi, to co najmniej trzy z nich muszą być w tym samym kolorze, powiedzmy zielonym.

Oznaczmy wierzchołki na drugich końcach tych krawędzi przez $\text{[math]}$ i przeanalizujmy kolorowanie powyższego układu (rysunek 1). Ponieważ krawędzie $\text{[math]}$ , $\text{[math]}$ oraz $\text{[math]}$ są zielone, to nadanie koloru zielonego którejkolwiek z krawędzi $\text{[math]}$ , $\text{[math]}$ lub $\text{[math]}$ spowoduje pojawienie się trójkąta w tym kolorze (odpowiednio $\text{[math]}$ , $\text{[math]}$ lub $\text{[math]}$ ). Z kolei, jeśli wszystkie mają kolor czarny, otrzymujemy czarny trójkąt $\text{[math]}$ , co kończy dowód. Λ

Warto jeszcze zauważyć, że w powyższym twierdzeniu liczby sześć nie możemy zmniejszyć, gdyż w grupie pięcioosobowej możemy tak dobrać układ znajomości, aby uniknąć monochromatycznego trójkąta (tak jak na rysunku 2).

Twierdzenie Ramseya

Nasuwa się pytanie, czy twierdzenie o sześciu osobach można uogólnić. Czy, jeżeli zamiast żądać pojawienia się jednokolorowej kliki trzyosobowej, zażądamy, aby taka klika składała się z czterech osób, to czy w odpowiednio dużej grupie musi się ona pojawić? Co wreszcie z ogólnym przypadkiem dowolnej kliki $\text{[math]}$ ? W 1930 ukazała się praca Franka Ramseya, w której udowodnił on bardzo daleko idące uogólnienie naszych rozważań, a szczególnym przypadkiem była odpowiedź na postawione wcześniej pytanie.

Twierdzenie 2 (Ramsey(1930)). Dla każdej liczby naturalnej $\text{[math]}$ istnieje taka liczba naturalna $\text{[math]}$ , że wśród dowolnych $\text{[math]}$ osób zawsze znajdziemy:

$\text{[math]}$: albo $\text{[math]}$ osób, które znają się wzajemnie (każda z każdą),
$\text{[math]}$: albo $\text{[math]}$ osób, które nie znają się wcale (żadna z żadną).

Najmniejsze takie $\text{[math]}$ , którego istnienie gwarantuje powyższe twierdzenie, oznaczamy przez $\text{[math]}$ i nazywamy k-tą liczbą Ramseya.

Można powiedzieć trochę filozoficznie, że twierdzenie Ramseya mówi o nieuchronności pojawiania się pewnych regularności w dużych strukturach. Dla każdego małego obiektu matematycznego możemy zawsze znaleźć odpowiednio dużą strukturę, w której obiekt ten musi się pojawić.

Liczby Ramseya i kosmici

Pojawia się następny naturalny problem: czy istnieje jakiś jawny wzór na kolejne liczby Ramseya, a jeśli nie, to czy można je chociaż efektywnie wyznaczać. Wiadomo, że $\text{[math]}$ (dwie osoby znają się bądź nie znają), pokazaliśmy też, że $\text{[math]}$ , ale już wykazanie, że $\text{[math]}$ nie jest sprawą łatwą. Po pierwsze, musimy pokazać, że istnieje dwukolorowanie krawędzi grafu $\text{[math]}$ , w którym unikniemy jednokolorowej kliki $\text{[math]}$ . Okazuje się, że kolorowanie takie jest wyznaczone jednoznacznie (z dokładnością do permutacji wierzchołków), a otrzymujemy je w ten sposób, że wierzchołkom grafu przypisujemy liczby $\text{[math]}$ z ciała $\text{[math]}$ , krawędź zaś malujemy na czarno wtedy i tylko wtedy, gdy różnica liczb na jej końcach jest kwadratem w tym ciele. Wykazanie, że w grafie $\text{[math]}$ takie kolorowanie jest niemożliwe, jest sprawą znacznie trudniejszą.

A ile wynosi $\text{[math]}$ ? Otóż, zaskakujące jest, że dokładna wartość piątej liczby Ramseya nie jest dotąd znana, co na pierwszy rzut oka wydaje się nieprawdopodobne. Wiadomo tylko, że $\text{[math]}$ . Któż z nas teraz nie zakrzyknie: od czego mamy nowoczesne komputery?! Czy przebadanie kolorowań grafu pełnego na zaledwie 43 wierzchołkach może w dzisiejszych czasach stanowić jakąkolwiek trudność? Gdy jednak przyjrzymy się problemowi bliżej i dokonamy kilku obliczeń, sprawa staje się jasna. Zauważmy, że graf $\text{[math]}$ ma $\text{[math]}$ krawędzie, więc chcąc przeanalizować ich wszystkie możliwe dwukolorowania, musielibyśmy rozpatrzyć $\text{[math]}$ (czyli około $\text{[math]}$ ) przypadków, a to już znacznie przekracza możliwości nawet najszybszych superkomputerów. Z kolejnymi liczbami Ramseya sprawa wygląda jeszcze gorzej: $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ . Naiwnością byłoby również sądzić, że mogą one się wyrażać jakimkolwiek jawnym wzorem.

Aby oddać skalę trudności problemu znajdowania liczb Ramseya, warto przypomnieć opowiastkę, którą często zwykł przytaczać Paul Erdős, a trudno chyba o większy autorytet w tej dziedzinie (opublikował on przeszło 100 prac dotyczących teorii Ramseya).

Wyobraźmy sobie, że wrogo nastawiona i znacznie potężniejsza militarnie obca cywilizacja napada na Ziemię i żąda od ludzi wyznaczenia dokładnej wartości liczby $\text{[math]}$ , gdyż w przeciwnym razie zniszczy planetę. Co powinniśmy zrobić, aby nie dopuścić do zagłady? Powinniśmy zmobilizować wszystkich matematyków, informatyków i programistów, zaprogramować wszystkie komputery na świecie i spróbować znaleźć żądaną wartość. A co, jeśli kosmici zażądają wyznaczenia liczby $\text{[math]}$ ? Wówczas powinniśmy spróbować…zniszczyć najeźdźców.

Musimy pogodzić się z tym, że, prawdopodobnie, nigdy nie dowiemy się, ile wynosi szósta, siódma i następne liczby Ramseya, co wcale nie znaczy, że ludzie zaprzestaną swych wysiłków w próbach ich wyznaczenia.