Przeskocz do treści

Delta mi!

O kapeluszach i pewnym pewniku

Tomasz Idziaszek

o artykule ...

  • Publikacja w Delcie: grudzień 2011
  • Publikacja elektroniczna: 01-12-2011

O ciekawych problemach związanych z kapeluszami pisaliśmy już w  Delcie nie raz, ale że dobrego nigdy za wiele, napiszemy też i w tym numerze, tyle że inaczej.

obrazek

Problem. W rzędzie stoi math osób i każdej z nich nałożony został na głowę biały lub czarny kapelusz. Każda widzi kapelusze tych osób, które stoją przed nim, zatem pierwsza osoba widzi kapelusze wszystkich pozostałych, natomiast ostatnia osoba nie widzi żadnego (rysunek). Oczywiście, nikt nie widzi swojego kapelusza i w tym cała zabawa, gdyż zadaniem każdej z osób jest odgadnięcie, jakiego koloru kapelusz ma na głowie. Uczestnicy zabawy odgadują po kolei, począwszy od pierwszej osoby w rzędzie, i każdy słyszy odpowiedzi poprzedników. Uznajemy, że się udało, jeśli błędnej odpowiedzi udzieliła nie więcej niż jedna osoba. A jak to z zabawami bywa, warto, by były udane. Z tego też powodu uczestnicy, przed nałożeniem kapeluszy na ich głowy, mogą się naradzić i ustalić wspólną strategię postępowania.

W tym momencie zachęcamy Czytelników do przerwania lektury i zastanowienia się, dla jakich math istnieje strategia gwarantująca wygraną.

Spróbujmy w następujący sposób: pierwsza osoba, nieważne, jak będzie się starać, ma 50% szans na odgadnięcie koloru swojego kapelusza. W pesymistycznym przypadku musimy więc założyć, że udzieli błędnej odpowiedzi i tym samym wykorzysta cały dostępny limit pomyłek. Pogodzeni z tym faktem, spróbujemy w jej odpowiedzi przemycić bit informacji dla pozostałych uczestników. Oznaczmy przez math kolor kapelusza math-tej osoby ( math jeśli jest to biały kapelusz, i  math jeśli kapelusz jest czarny), a przez math liczbę czarnych kapeluszy, które math-ta osoba widzi przed sobą.

Zrobimy teraz tak: pierwsza osoba mówi „biały”, jeśli math jest parzyste, a w przeciwnym przypadku mówi „czarny”. Co nam z tego przyjdzie? Ano tyle, że ta informacja wystarczy, by druga osoba bezbłędnie odgadła kolor swojego kapelusza. W istocie, ponieważ math zatem usłyszawszy przed chwilą wartość math bez trudu wyznaczy ona math Co więcej, każda kolejna osoba może postąpić podobnie, korzystając z faktu, że

display-math

oraz z tego, że zna wartości math oraz math Potrafimy więc znaleźć strategię dla dowolnie dużego math I tu nasuwa się pytanie: a co, jeśli math byłoby nieskończone? Innymi słowy, mamy nieskończony rząd osób, w którym math-ta osoba widzi kapelusze wszystkich osób o większych numerach (jest ich, oczywiście, nieskończenie wiele). Czy i tym razem będzie istniała strategia? Podkreślmy, że nie osłabiamy żadnej z reguł zabawy, zatem nadal dopuszczamy tylko jedną pomyłkę. Zauważmy też, że nasza strategia dla skończonego math nie będzie tu działać, gdyż math może nie być liczbą naturalną.

Odpowiedź jest nieco zaskakująca: strategia istnieje. Po raz drugi zachęcamy Czytelników, aby przez (być może dłuższą) chwilę zmierzyli się z tym zadaniem samodzielnie.

Nieskończony ciąg math kolorów kapeluszy oznaczać będziemy przez math Powiemy, że dwa nieskończone ciągi math i math  są w relacji math jeśli różnią się na skończenie wielu pozycjach. Piszemy więc math jeśli zbiór math jest skończony. Łatwo przekonać się, że tak zdefiniowana relacja math  jest relacją równoważności. I teraz z pomocą przychodzi nam wspomniany w tytule pewien pewnik, a konkretnie pewnik wyboru – nieocenione źródło matematycznych paradoksów. Dzięki niemu możemy dla każdej klasy abstrakcji relacji math  wybrać jej reprezentanta i poinformować wszystkich o tym, który został wybrany. Innymi słowy, istnieje taka funkcja math określona na zbiorze wszystkich ciągów kolorowań kapeluszy, która dla dowolnego math spełnia math oraz dla dowolnych math jeśli math to math Zauważmy teraz, że jeśli uczestnicy porozumieją się co do wyboru funkcji math to każdy z nich będzie mógł obliczyć ten sam ciąg math gdyż nie zna on tylko skończonej liczby wyrazów ciągu math Zauważmy też, że jeśli teraz math-ty zawodnik odpowie math (nawet nie czekając na odpowiedzi poprzedników), to ponieważ math więc będziemy mieli tylko skończoną liczbę pomyłek.

W tym momencie spróbujemy wyeliminować te pomyłki metodą analogiczną jak w przypadku skończonym. Oznaczmy przez math zbiór numerów osób (poza pierwszą), których kolory kapeluszy math nie zgadzają się z kolorami w ciągu math czyli math Skoro math to zbiór math jest skończony. Niech math będzie liczbą osób ze zbioru math które widzi osoba math Niech też math jeśli math oraz math gdy math Każda z osób (poza pierwszą) musi zdecydować, czy nie należy do zbioru math i wtedy odpowiada zgodnie z math czy też należy (i wtedy musi odpowiedzieć przeciwnie). Pierwsza osoba podaje math Druga osoba wie, że math jest więc w stanie wyznaczyć math stwierdzić, czy należy do math i odpowiedzieć poprawnie. Analogicznie math-ta osoba oblicza math z zależności

display-math

oraz z faktu, że math dla math jest równe 1 wtedy i tylko wtedy, gdy math-ta osoba udzieliła odpowiedzi niezgodnej z wartością math I to by było na tyle, gdyby nie to, że pokazując istnienie strategii dla math otwieramy drogę kolejnym pytaniom: a co, jeśli math jest liczbą porządkową większą niż math ? Zastanówmy się więc nad istnieniem strategii w przypadku math  (czyli za nieskończonym rzędem osób stoi jeszcze jeden uczestnik o numerze math  który odpowiada na samym końcu). Czytelnik znów zdecyduje, na jak długo przerwać w tym miejscu lekturę.

Wydawać by się mogło, że nie da się uniknąć co najmniej dwóch pomyłek, gdyż osoba math  nie widząc nikogo innego, musi wprost otrzymać kolor swojego kapelusza, co wymagałoby przekazania dodatkowego bitu informacji. Jednak nie należy zapominać o tym, że usłyszała ona odpowiedzi wszystkich pozostałych uczestników, zatem zna kolory kapeluszy math (wszak ci uczestnicy odpowiadali poprawnie). Jest zatem w stanie obliczyć ciąg math i tym samym zbiór math W tym momencie łatwo już jest zmodyfikować strategię: pierwsza osoba zamiast math podaje math  Pozostałe osoby o numerach naturalnych, widząc math  są w stanie odzyskać math  i grać jak poprzednio. Natomiast uczestnik math  znając math  bez trudu oblicza math

Łatwo wskazać, jak zmodyfikować powyższą strategię, by działała w przypadku math   math  a nawet math  A jaką strategię zastosować dla math ? A math ? A może dla każdej liczby porządkowej można wskazać analogiczną strategię? Wreszcie, co w przypadku, gdy mamy więcej kolorów kapeluszy?