Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. Bogdan w więzieniu | Politechnika Gdańska

Zagadka 1

W celi Bogdana znajduje się 10 więźniów. Komendant więzienia poinformował skazanych, że następnego ranka strażnicy wyprowadzą ich na dziedziniec, ustawią
w szeregu, nałożą im na głowy czarne bądź białe kapelusze i zrobią to w taki sposób, że każdy z nich będzie widział wyłącznie kapelusze osób stojących przed nim. Wobec tego ostatni będzie widział 9 kapeluszy, przedostatni 8 itd. Poczynając od ostatniego, każdemu skazańcowi zostanie postawione pytanie o kolor jego kapelusza. Jeśli odpowie prawidłowo, uratuje swoje życie, jeśli nie – zginie. Bogdan, jako najinteligentniejszy z nich, musi opracować strategię pozwalającą na uratowanie maksymalnie wielu więźniów. Jaka to strategia?

Rozwiązanie
Na początek dobra wiadomość: Bogdanowi udało się zająć miejsce w środku szeregu. Ale przejdźmy do rozwiązania. Pierwszy pomysł jest taki, by każdy więzień stojący na parzystej pozycji podpowiedział kolor kapelusza więźniowi, który stoi przed nim. Wówczas uratuje się przynajmniej połowa z nich. Można jednak postąpić tak, że uratują się prawie wszyscy. Mianowicie Bogdan ustalił, że ostatni z nich odpowie: czarny, gdy zobaczy zero lub parzystą liczbę czarnych kapeluszy, bądź biały, gdy zobaczy nieparzystą liczbę czarnych kapeluszy. Wówczas każdy kolejny z nich, słysząc tę odpowiedź, wydedukuje, jakiego koloru kapelusz ma on sam na głowie. To znaczy, jeśli usłyszy za sobą czarny, a będzie widział nieparzystą liczbę czarnych kapeluszy u swoich poprzedników, to odpowie czarny. W przeciwnym razie powie biały. Analogicznie będzie rozumował każdy następny więzień. Dzięki temu cała dziesiątka będzie miała co najmniej 95 proc. szans na przeżycie. Jedynym, który może zginąć, będzie ostatni w szeregu.

Uwaga 1.
Zagadka z kapeluszami może być uogólniona na dowolną liczbę więźniów i kapeluszy o dowolnych kolorach (byle wystarczyło kapeluszy, bo więźniów raczej nie zabraknie).

Zagadka 2

W więzieniu, w którym ciągle przebywa Bogdan, jest 100 więźniów. Zarząd więzienia chce się ich pozbyć. Wymyśla więc następującą grę: Zamyka wszystkich skazańców w celi A. Strażnicy w pokoju B ustawiają pod jedną ze ścian 100 zamkniętych szufladek. Do każdej szufladki wkładają dokładnie jedną karteczkę. Na każdej karteczce jest nazwisko innego więźnia. Karteczki wkładane są do pojemników zupełnie losowo. O pewnej godzinie spośród więźniów zgromadzonych w celi A zostanie losowo wybrany jeden skazaniec, który razem ze strażnikiem wejdzie do pustego pokoju B. Tam wskaże jedną z szufladek. Strażnik otworzy ją, przeczyta na głos, co jest na karteczce, i w niezmienionym stanie odłoży do pojemnika. Jeżeli nie wyczytał nazwiska skazanego, to może on wybrać kolejną szufladkę. Więzień ma łącznie 50 takich szans. Jeżeli któryś współwięzień zmarnuje wszystkie swoje szanse, to on i wszyscy jego towarzysze niedoli zginą. Jeśli na odczytanej przez strażnika kartce będzie nazwisko więźnia, to trafi on do sali C, bez kontaktu z celą A. Wtedy procedura powtarza się i wybierany jest kolejny więzień. Powtórzmy raz jeszcze, więźniowie przeżyją tylko wtedy, gdy wszyscy trafią do sali C, tj. wszyscy prawidłowo odgadną swoje pojemniki. Jaką strategię powinni przyjąć więźniowie, aby zwiększyć swoje szanse na przetrwanie?

Rozwiązanie
Zagadka jest bardzo trudna, a oszacowanie szansy na przeżycie 100 więźniów jeszcze trudniejsze. Zauważmy najpierw, że gdyby każdy więzień wybierał szuflady na chybił trafił, to prawdopodobieństwo, iż dowolny z nich znajdzie w końcu swoje nazwisko wynosi 0,5100 ≈ 10-30. Zacznijmy więc od tego, że więźniowie sporządzą alfabetyczny spis swoich nazwisk i ponumerują się zgodnie z pozycją na liście. Każdy z nich musi nauczyć się tej listy na pamięć. Pierwszy wylosowany więzień wskazuje szufladkę opatrzoną jego własnym numerem. Jeśli natrafi na swoje nazwisko, przechodzi do sali C. Jeśli nie, to jako następną wskazuje szufladkę o numerze zgodnym z nazwiskiem ostatnio wylosowanego więźnia (rys. 1). Oczywiście istnieje możliwość, że po 50 próbach nie znajdzie pojemnika ze swoim nazwiskiem. Ale prawdopodobieństwo takiego zdarzenia jest równe temu, że w losowo wygenerowanej permutacji 100 elementów istnieje cykl długości większej niż 50 i wynosi ono prawie 69 proc. (ściślej, dąży do logarytmu naturalnego z 2). Jeśli takiego cyklu nie ma, to zarówno on, jak i wszyscy więźniowie wygrają, a szansa na to przekracza 31 proc.

Podziękowanie

Autor dziękuje panu prof. Krzysztofowi Goczyle za inspirujące dyskusje i panu mgr. inż. Janowi Wojtkiewiczowi za pomoc graficzną okazaną w trakcie tworzenia tego cyklu potyczek algorytmicznych.

Marek Kubale
kubale@eti.pg.edu.pl