Strona główna / Popularnonaukowe / Histerie matematyczne. Gry i zabawy z matematyką

Aktualności

24.09.2021

Spotkanie online Pauliną Młynarską

W piątek 24 września o godz. 20:00 zapraszamy na wirtualne spotkanie z Pauliną Młynarską, autorką książki "Moja lewa joga".

Wywiady

25.08.2021

"Tajemnica Wzgórza Trzech Dębów". Wywiad z Piotrem Borlikiem

Zapraszamy do przeczytania wyjątkowego wywiadu z Piotrem Borlikiem. Z autorem książki "Tajemnica Wzgórza Trzech Dębów" rozmawiał Marcin Waincetel z Lubimyczytac.pl.

Posłuchaj i zobacz

18.09.2021

Rozmowa z Anną Karpińską

Zapraszamy do wysłuchania podcastu z Anną Karpińską, autorką książki "Kiedy nadejdziesz".

Bestsellery

TOP 20

  1. Billy Summers Stephen King
  2. Martwiec Katarzyna Puzyńska
  3. Red, White & Royal Blue Casey McQuiston

Histerie matematyczne. Gry i zabawy z matematyką

Ian Stewart

Rozdział 1

 

On wie,
że ja wiem,
że on wie...

 

Czasem nie wystarczy po prostu
coś wiedzieć - trzeba jeszcze
wiedzieć, że ktoś inny wie.
Albo że ktoś inny wie, że my wiemy, że on wie, że...
Takie rozważania prowadzą
do pojęcia „wspólnej wiedzy”.
Gdy coś stanie się już wspólną
wiedzą, można wnioskować o tym, co wnioskują inni.

Niezwykle uprzejmi mnisi z zakonu Zdumiewitów lubią się nawzajem zadziwiać różnymi sztuczkami logicznymi. Pewnej nocy, brat Jonasz zakrada się do celi, w której śpią bracia Archibald i Benedykt, i każdemu z nich na czubku wygolonej głowy maluje niebieską plamę. Po przebudzeniu każdy z nich widzi oczywiście plamę na głowie drugiego, ale - jako człowiek uprzejmy - nic nie mówi. Każdy zastanowia się, czy sam też ma na głowie plamę, ale jest zbyt uprzejmy, żeby o to spytać. I wtedy właśnie brat Zenon, który nigdy nie zdołał do końca nauczyć się, co to jest takt, zaczyna chichotać. Zapytany, o co chodzi, przypomina sobie o dobrych manierach i odpowiada enigmatycznie:

- Co najmniej jeden z was ma niebieską plamę na głowie.

Oczywiście, każdy z mnichów i tak to wie. Archibald zaczyna myśleć: „Ja wiem, że Benedykt ma niebieską plamę na głowie, ale on nie wie, że... Czy ja mam plamę? Przypuśćmy, że nie mam. W takim razie Benedykt może zobaczyć, że ja nie mam plamy, więc z uwagi Zenona powinien natychmiast wywnioskować, że to on ma plamę na głowie. Ale Benedykt nie zdradza żadnych oznak zawstydzenia - oj, to znaczy, że ja muszę mieć plamę na głowie”. I w tej chwili czerwienieje ze wstydu. Benedykt czerwienieje również, w tej samej chwili i z tego samego powodu.

Bez niewinnej uwagi Zenona, żaden z nich nie mógłby rozpocząć swego rozumowania. A mimo to Zenon nie powiedział im nic, czego - jak się wydaje - obaj i tak już by nie wiedzieli.

Jeszcze bardziej zagadkowy efekt otrzymujemy, rozważając trzech mnichów. Tym razem w celi śpią Archibald, Benedykt i Cyryl; Jonasz maluje każdemu z nich niebieską plamę na głowie. Po przebudzeniu każdy z mnichów widzi plamy na głowach obu pozostałych, ale nic nie mówi. Ten logiczny impas przerywa dopiero wypowiedź Zenona, który wywołuje sensację:

- Co najmniej jeden z was ma niebieską plamę na głowie.

Archibald zaczyna wtedy myśleć i myśli sobie mniej więcej tak. „Przypuśćmy, że ja nie mam plamy na głowie. Wtedy Benedykt widzi plamę tylko na głowie Cyryla, a na mojej głowie - nic, i może sam sobie zadać pytanie, czy ma plamę na głowie. I może rozumować tak: „Jeśli ja, Benedykt, nie mam plamy, to Cyryl widzi, że ani Archibald, ani Benedykt nie ma plamy, i może stąd natychmiast wywnioskować, że sam ma plamę na głowie. Ale skoro Cyryl, który jest świetnym logikiem, miał mnóstwo czasu, żeby o tym pomyśleć, a nie zdradza oznak zawstydzenia, to ja, Benedykt, muszę mieć plamę na głowie”. A ponieważ Benedykt również jest świetnym logikiem, myśli Archibald, i miał mnóstwo czasu, żeby o tym pomyśleć, a mimo to nie zdradza oznak zawstydzenia, więc wynika stąd, że ja, Archibald, jednak mam plamę na głowie”. I w tej chwili Archibald czerwienieje ze wstydu. Benedykt i Cyryl również, bo każdy z nich przeprowadził analogiczne rozumowanie.

Ten sam argument działa dla czterech, pięciu i większej liczby mnichów - ponownie, przy założeniu, że każdy z nich ma plamę na głowie. Wnioskowania stają się coraz bardziej zawiłe, ale niezależnie od tego, ilu jest mnichów, ogłoszenie „co najmniej jeden z was ma plamę na głowie” wywołuje łańcuch dedukcji, prowadzący wszystkich do konkluzji, że sami też mają plamę na głowie. Gdy liczba mnichów rośnie, rzeczą pomocną staje się zegar, służący do synchronizacji wnioskowań. Za chwilę, gdy zaczniemy wyjaśniać, co się tu dzieje, wprowadzę takie urządzenie do rozważań. Podobnie paradoksalne rzeczy dzieją się wtedy, gdy niektórzy mnisi mają plamy na głowie, a niektórzy nie - wrócę jeszcze do tej kwestii.

Jest wiele łamigłówek tego typu. Mówi się w nich o dzieciach z brudnymi twarzami, uczestnikach przyjęć noszących dziwne kapelusze, o dwóch osobach, które są w posiadaniu kolejnych liczb całkowitych, ale nie wiedzą, kto z nich ma większą, wreszcie - w wersji raczej politycznie niepoprawnej - o niewierności małżeńskiej wśród mieszkańców pewnej wyspy. Wszyskie te łamigłówki są dość zdumiewające, ponieważ zapłon całej procedury stanowi czyjeś obwieszczenie faktu, który i tak jest doskonale oczywisty dla wszystkich. Jeśli jednak starannie przeanalizujemy to, co się dzieje, przekonamy się, że owo obwieszczenie w istocie ujawnia nową informację. To nieformalny język, często tak pomocny, zaciemnia w tym przypadku sprawę.

Wróćmy do pierwszego przykładu dwóch mnichów. Zenon oświadcza:

- Co najmniej jeden z was ma niebieską plamę na głowie.

Co mnisi naprawdę wiedzą? Otóż Archibald wie, że Benedykt ma plamę na głowie, a Benedykt wie, że Archibald ma plamę na głowie. Są to jednak różne informacje. Gdy Archibald słyszy wypowiedź Zenona i stwierdza, że już to przecież wie, jego „kimś” jest Benedykt. Ale gdy Benedykt słyszy wypowiedź Zenona i stwierdza, że już to przecież wie, jego „kimś” jest Archibald. To wcale nie to samo stwierdzenie. Oświadczenie Zenona nie polega jedynie na przekazaniu Archibaldowi informacji, że ktoś ma plamę na głowie. Ono również informuje Archibalda, że Benedykt wie teraz, że ktoś ma plamę nałowie - i że jest to ten sam ktoś. Zatem oświadczenie Zenona nie mówi Archibaldowi nic nowego o tym, co Archibald wie, natomiast mówi Archibaldowi coś nowego o tym, co wie Benedykt.

Zagadki logiczne tego typu są znane jako łamigłówki ze „wspólną wiedzą” i wszystkie opierają się na tym samym mechanizmie. To nie treść wypowiedzi jest ważna, ważne jest to, że każdy wie, iż wszyscy tę wypowiedź słyszeli. Gdy wypowiedziany fakt staje się wspólną wiedzą, można myśleć o tym, jak inni nań zareagują.

Wróćmy jednak do mnichów. Przypuśćmy, że każdy ze 100 mnichów ma plamę na głowie i każdy jest świetnym, błyskawicznie wnioskującym logikiem. Aby spróbować zsynchronizować ich myśli, załóżmy, że opat ma dzwonek.

- Co dziesięć sekund - powiada opat - użyję tego dzwonka. Będziecie więc mieli mnóstwo czasu, by przeprowadzić wszelkie niezbędne rozumowania. Gdy tylko dzwonek przebrzmi, wszyscy ci z was, którzy zdołają wywnioskować, że sami mają plamę na głowie, mają podnieść ręce do góry.

Czeka dziesięć minut w ciszy, przerywanej co dziesięć sekund dźwiękiem dzwonka, ale nic się nie dzieje.

- Ach, co za głupiec ze mnie. Zapomniałem o jednej informacji: co najmniej jeden z was ma plamę na głowie.

Następnie po każdym z 99 kolejnych dzwonków nic się nie dzieje, a po setnym dzwonku cała setka mnichów równocześnie podnosi ręce do góry.

Istota rozumowania jest następująca. Mnich numer 100 widzi, że każdy z 99 pozostałych ma plamę na głowie. „Jeśli ja nie mam plamy”, myśli sobie, „to każdy z tych 99 o tym wie. To wyłącza mnie z wszelkich wnioskowań. Zatem oni przeprowadzają wszystkie te rozumowania, z którymi mamy do czynienia w przypadku 99 mnichów, to znaczy wtedy, gdy ja nie mam plamy. Jeśli prawidłowo wyjaśniłem łamigłówkę o 99 mnichach, to po 99 dzwonku wszyscy podniosą ręce do góry”. I czeka na 99 dzwonek, po którym nic się nie dzieje. „Ach, więc moje założenie jest fałszywe - zatem muszę mieć plamę na głowie”. Dzwonek nr 100, ręka w górę. Tak samo jest z każdym z pozostałych mnichów.

Łamigłówkę o 99 mnichach (przy hipotetycznym założeniu, że mnich nr 100 nie ma plamy na głowie) wyjaśnia się tak samo: tym razem mnich nr 99 oczekuje, że każdy z pozostałych 98 podniesie rękę do góry po 98 dzwonku - chyba że mnich nr 99 ma plamę na głowie. I tak dalej, rekurencyjnie, aż dojdziemy do pojedynczego hipotetycznego mnicha, który nigdzie dookoła nie widzi żadnych plam na głowie, ze zdumieniem dowiedział się, że ktoś ma plamę na głowie, natychmiast wnioskuje, że to musi być on sam, więc po pierwszym dzwonku podnosi rękę do góry.

To jeden z przypadków zastosowania zasady indukcji matematycznej, która orzeka, że jeśli pewna własność liczb całkowitych zachodzi dla n = 1, a ponadto z założenia jej prawdziwości dla liczby n wynika jej prawdziwość dla liczby n + 1, i tak jest dla każdego n, to wtedy owa własność zachodzi dla każdego n.

Do tej pory zakładałem, że każdy z mnichów ma plamę na głowie, ale przeprowadzając podobne rozumowanie możecie się przekonać, że nie jest to wcale istotny wymóg. Przypuścmy na przykład, że 68 ze 100 mnichów ma plamy na głowach. Wtedy, i jest to całkowicie logiczne, nic nie dzieje się do 68. dzwonka, po którym wszyscy z plamami na głowach podnoszą ręce do góry, a wszyscy pozostali - nie.

Łamigłówki ze wspólną wiedzą były przedmiotem rozległych badań; ciekawe odnośniki do literatury można znaleźć w artykule Davida Gale'a (patrz „Spis polecanych lektur” zamieszczony na końcu książki). Najbardziej matematyczny, a zarazem najbardziej dalekosiężny przykład opisany w tym artykule pochodzi od Johna Conwaya (Uniwersytet w Princeton) i Michaela Patersona (Uniwersytet w Warwick, Wielka Brytania). Wyobraźmy sobie Herbatkę Szalonych Matematyków. Każdy z uczestników ma na głowie kapelusz, na którym napisano pewną liczbę. Jest to liczba nieujemna, ale nie musi to wcale być liczba całkowita. Ponadto, liczba jednego z graczy musi być różna od zera. Załóżmy, że żaden z graczy nie widzi własnej liczby, ale widzi liczby wszystkich pozostałych.

Teraz - element wspólnej wiedzy. Do ściany przypięta jest lista liczb. Jedna z tych liczb jest sumą wszystkich liczb na kapeluszach - ale nikt nie wie, która. Załóżmy też, że liczba pozycji (tzn. możliwych sum) na liście nie przekracza liczby graczy.

Co dziesięć sekund dzwoni dzwonek i każdy, kto zna już własną liczbę - lub, równoważnie, umie poprawnie podać wartość sumy wszystkich liczb, bo przecież każdy widzi liczby wszystkich pozostałych - musi ten fakt obwieścić publicznie. Conway i Patterson udowodnili, że w końcu któryś z graczy istotnie dokona takiego obwieszczenia, popartego niezbitą logiką.

Na pierwszy rzut oka brzmi to paradoksalnie. Załóżmy na przykład, że graczy jest trzech i każdy z nich ma na kapeluszu liczbę 2, a lista na ścianie zawiera liczby 6, 7, 8. Każdy z graczy widzi sumę częściową 2 + 2 na dwóch pozostałych kapeluszach, zatem każdy wie, że sam ma na kapeluszu 2, 3 lub 4. Każdy z dwóch pozostałych graczy widzi zatem sumę częściową 2 + 2, 2 + 3 lub 2 + 4, a więc każda z sum 6, 7, 8 jest możliwa (pamiętajmy: niektórzy gracze - ale nie wszyscy! - mogą mieć na kapeluszach zera). To oznacza, że żadnej z sum nie można wykluczyć. Jednak dzięki dzwonkowi gracze mogą wyciągać wnioski z faktu, że nikt z pozostałych do tej pory nie obwieścił, że zna swoją liczbę. Po każdym dzwonku pewne układy liczb można wykluczyć, co prowadzi do nieoczekiwanego wniosku Conwaya i Patersona.

Aby zrozumieć, na czym ten paradoks polega, rozważmy dwóch graczy i przypuśćmy, że do ściany przypięta jest lista: 6, 7. Składników nie znamy, nazwijmy je więc x i y. Obaj gracze wiedzą, że x + y = 6 lub x + y = 7. Pora teraz na odrobinę geometrii. Pary liczb spełniających któryś z tych dwóch warunków są współrzędnymi punktów dwóch odcinków położonych w pierwszej ćwiartce układu współrzędnych na płaszczyźnie (rysunek 1a).

Jeśli x albo y jest większe od 6, to gra kończy się po pierwszym dzwonku, gdyż jeden z graczy widzi od razu, że suma 6 nie jest możliwa. Pary (x,y), dla których tak właśnie się dzieje, wskazano na rysunku 1b. (Potrzebna jest odrobina ostrożności: punkty (1,6) i (6,1), tzn. końce zaznaczonych odcinków, nie zostały wyeliminowane z rozważań. Eliminowane są odcinki, którym brakuje jednego końca - tego, który znajduje się bliżej środka nachylonej linii). Jeśli żaden z graczy nie zareaguje po pierwszym dzwonku, te możliwości zostają wyeliminowane. Gra kończy się po drugim dzwonku, jeśli x albo y jest mniejsze od 1. Dlaczego? Któryś z graczy widzi wtedy kapelusz z liczbą mniejszą od 1 i wie już, że na swoim kapeluszu ma liczbę 6 lub mniejszą, zatem suma 7 jest wykluczona. Pary liczb, dla których gra kończy się po drugim dzwonku, wskazano na rysunku 1c. Rozumując dalej podobnie, widzimy, że pary (x,y), dla których gra kończy się po danym dzwonku, tworzą kolejne przekątne dwóch „schodkowych” łamanych, z których jedna schodzi w dół z lewej strony od góry, druga zaś wchodzi pod górę z prawej strony od dołu (patrz rysunek 1d). Te ukośnie położone odcinki szybko wyczerpują wszystkie możliwości. W istocie, w tym przypadku gra zakończy się najpóźniej po ósmym dzwonku. (Z powodu wspomnianych wyżej brakujących końców, układ liczb (3,3) wymaga ośmiu dzwonków, a każdy inny - siedmiu lub mniej).

Podobne rozumowanie pozwala rozstrzygnąć kwestię dowolnej listy sum dla dwóch graczy; pozwala też wyznaczyć maksymalną liczbę dzwonków, jaka może być konieczna do zakończenia gry. Dla większej liczby graczy dowód jest bardzo prosty, ale dość wyrafinowany matematycznie; artykuł Gale'a zawiera wszystkie szczegóły. Czytelnicy mogą zmierzyć się z zadaniem samodzielnego wyjaśnienia wspomnianego wcześniej przypadku trzech graczy, z których każdy ma na kapeluszu 2, a lista możliwych sum to 6, 7, 8. Oto prawidłowa konkluzja: przez 14 dzwonków nic się nie dzieje, a po piętnastym każdy z graczy oświadcza, jaka jest jego liczba.