Więźniowie z kapeluszami

[Aman]

Witam, próbuję rozgryźć takową zagadkę:

20-stu więźniów stoi na schodach. Każdemu założono na głowę kapelusz, biały lub czarny. Każde zdarzenie przydziału kapelusza jest niezależne, tzn. nie ma określonej ilości kapeluszy białych i czarnych. Oznacza to,że wszyscy mogą mieć skrajnie kapelusze białe lub czarne.
Więźniowie stoją w taki sposób, że każdy więzień widzi tylko kapelusze więźniów znajdujących się poniżej. Jeśli więzień dobrze zgadnie jaki kapelusz ma na głowie, jest mu darowane życie. W innym przypadku zostaje stracony.

Przed tą "egzekucją" więźniowie wspólnie ustalili algorytm, który ma ocalić jak największą liczbę z nich, wyłączając przy tym czynnik losowy. Teraz pytanie: Jak dużo więźniów zawsze uda się ocalić?


Moja analiza:
Na pierwszy rzut oka liczba ta waha się pomiędzy 10-19, ponieważ więzień na samej górze musi poświęcić się dla uzyskania jakiejkolwiek informacji. Każdy kolejny więzień (poza ostatnim na dole) ma dwie informacje :
-to co usłyszy od poprzednika
-to co widzi przed sobą u więźniów poniżej

Wymyśliłem, że jeśli więźniowie umówią się na hasło (biały-dwoje przede mną ma tego samego koloru kapelusze, czarny - mają różne kapelusze) to w ten sposób możemy ocalić 2 więźniów na 3, co daje nam 12 ocalonych na 18 + 2 więźniów, w których działa czynnik losowy.

Pamiętajmy, że musimy wykluczyć prawdopodobieństwo!
Czy macie jakieś inne pomysły? Czy 12 to będzie maksymalna (pewna) liczba?

[mostostalek]

biały-dwoje przede mną ma tego samego koloru kapelusze. Ale jakie? nie uratujesz w ten sposób dwóch na trzech więźniów.
Nie ulega wątpliwości, że na pewno uda się uratować połowę więźniów prostym algorytmem. Co drugi więzień mówi jaki kapelusz ma więzień przed nim. Zauważmy, że ostatni więzień widzi 19 kapeluszy. Może powiedzieć zatem kolor przeważający. Ale przeważający kolor może miec tylko 10/19 więźniów..

[Jan Kraszewski]

Można spokojnie ocalić 19 więźniów.

Wskazówka: parzystość.

JK

[mostostalek]

yyy.. jak jednym słowem podać dwie informacje??

[jarek4700]

Moim zdaniem \(\displaystyle{ 10}\) to największa liczba. Każdy więzień może albo ratować siebie albo podać jakąś informację o pozostałych.
Żeby jednoznacznie określić zbiór \(\displaystyle{ k}\) więźniów (można to sobie przedstawić jako ciąg binarny) trzeba podać \(\displaystyle{ k}\) bitów informacji.
Stąd nie możemy uratować jedenastu, bo nie ma następnych jedenastu żeby podać wystarczającą ilość informacji.


Jednak nie:
Można uratować wszystkich, oprócz ostatniego. Ostatni podaje kolor kapeluszy, których jest przed nim parzysta liczba. Zatem 19 wie jaki ma kolor kapelusza bo widzi resztę przed sobą. Teraz 18 wiedząc jakich kapeluszy było parzysta ilość w pierwszych 19 i znając odpowiedź 19-ego też wie jaki ma kapelusz itd.

Czyli więźniowie mogą jednak jednocześnie i uratować siebie i podać informację.

[Jan Kraszewski]

Pierwszy więzień w ustalony sposób informuje o parzystości liczby białych kapeluszy, które widzi (np. biały - widzę parzystą liczbę białych kapeluszy). Więzień pod nim bez problemu stwierdza, jaki ma kapelusz na głowie, porównując parzystość liczby widzianych białych kapeluszy z otrzymaną od pierwszego więźnia informacją. Podobnie każdy następny więzień nie ma tego problemu, bo wie, że wszyscy więźniowie od drugiego począwszy podawali kolor kapelusza, który mają na głowie. I tak uratują się wszyscy od drugiego (a pierwszy - jak ma szczęście )

JK