jump to navigation

Zagadka o więźniach i kapeluszach 06/02/2011

Posted by Mikołaj Morzy in humor, zagadki.
trackback

A question mark imageW trakcie zajęć z eksploracji danych zadaję studentom zagadki. To forma gimnastyki umysłowej i zabawy, chociaż staram się zbierać jedynie zagadki które są ściśle związane z informatyką. Wygląda na to, że będę musiał zacząć głębiej poszukiwać źródeł inspiracji. W tym tygodniu wygrzebałem piękną zagadkę, której reperkusje idą daleko dalej, niż początkowo sądziłem. Nawet New York Times pisał o niej. Zagadka jest następująca:

15 więźniów jest przetrzymywanych w więźeniu, którego naczelnikiem jest matematyk-sadysta. Pewnego dnia więźniowie dowiadują się o czekającej ich następnego dnia egzekucji, przy czym naczelnik pozwala im naradzić się przez noc w celu opracowania protokołu. Zasady egzekucji są następujące:

  • każdy więzień dostanie na głowę czapkę białą lub czarną na podstawie wyniku rzutu monetą (tj. prawdopodobieństwo uzyskania czapki białej jest takie samo jak prawdopodobieństwo uzyskania czapki czarnej i wynosi w obu pyrzpadkach 50%)
  • nie istnieje żaden sposób aby więzień zobaczył kolor swojej czapki
  • każdy więzień widzi kolory czapek wszystkich pozostałych więźniów
  • nie istnieje absolutnie żaden sposób komunikacji między więźniami (słowa, gesty, chrząknięcia, itp.)
  • zapytany o kolor swojej czapki, więzień może powiedzieć jedynie: biała, czarna lub odmówić odpowiedzi
  • jeśli każdy więzień odmówi odpowiedzi, wszyscy zostaną rozstrzelani
  • jeśli którykolwiek więzień pomyli się co do koloru swojej czapki, wszyscy zostaną rozstrzelani

Innymi słowy, więźniowie przeżyją tylko wtedy, jeśli co najmniej jeden z nich poda kolor czapki i wszyscy, którzy się odezwą, zgadną poprawnie. Jakie szanse na przeżycie mają więźniowie?

Naiwna strategia jest taka, że wszyscy milczą, a uzgodniony więźnień podaje losowy kolor, np. biały. Taki protokół gwarantuje im 50% szans na przeżycie. Okazuje się, że można dużo dużo dużo lepiej. Co jeszcze ciekawsze, im więcej więźniów, tym lepiej, ich szanse zdecydowanie rosną. Jeden z moich studentów podesłał mi bardzo ciekawą dyskusję wraz z rozwiązaniem, autorstwa Andrzeja Dąbrowskiego z Instytutu Matematycznego Uniwersytetu Wrocławskiego, a także artykuł „Why Mathematicians Now Care About Their Hat Color„, który ukazał się w NYT parę lat temu.

Komentarze»

1. oskar - 04/23/2012

mozg eksplozja

2. Gosia - 03/12/2014

Czyli moga w wybranej kolejnosci odpowiadac? Jesli tak to:
w jednym z kolorow bedzie co najmniej 8 kapeluszy, zatem kazdy kto widzi co najmniej osiem kapeluszy w ktoryms z kolorow mowi pass. Pass powiedza wszyscy oprocz ostatnich osmiu (bez wzgledu na to czy kapeluszy w danym kolorze bylo 8 czy wiecej. I teraz wszyscy pozostali maja ten sam kolor – czyli ktorykolwiek mowi kolor jaki widzi u pozostalych siedmiu.

Mikołaj Morzy - 03/23/2014

Ten protokół nie zadziała. Jeśli na początku jest 10 białych kapeluszy i 5 czarnych, to pierwszy więzień (niezależnie od koloru swojego kapelusza) mówi „pass”, podobnie drugi, trzeci, itd. Zgodnie z podaną recepturą *każdy* więzień powie „pass”, bo każdy więzień widzi dokładnie to samo.


Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d bloggers like this: