[zefciu]

Jest sobie Królewna Śnieżka i 36 krasnoludków. Pewnego dnia postanowiła zagrać w makabryczną grę. Ustawiła krasnoludki jeden za drugim tak, że pierwszy krasnoludek widzi wszystkie przed sobą, drugi nie widzi pierwszego, ale widzi resztę, itd., po czym nałożyła im na głowy czapeczki. Czapeczki występują w 2 kolorach: czerwonym i zielonym. Nastepnie Królewna podchodzi po kolei do każdego krasnoludka, począwszy od pierwszego, i zadaje pytanie: "jaki jest kolor twojej czapeczki?". Jeśli odpowie dobrze - przeżywa. Jeśli źle, Królewna podrzyna mu gardło. Przed rozstawieniem i założeniem czapeczek Królewna pozwala krasnoludkom się naradzić, by ustalić strategię. Jak powinna wyglądać ta strategia, by przeżyło jak najwięcej krasnoludków?

Pierwszy krasnoludek swoją odpowiedzią ma zakodować, czy widzi przed sobą parzystą, czy nieparzystą liczbę jakichś czapeczek. Np. mogą się umówić, że jeśli widzi parzystą liczbę czerwonych, to mówi „czerwona”, a jeśli nieparzystą „zielona”. Następny krasnoludek, jeśli widzi przed sobą taką samą liczbę czerwonych, jak wynika z wypowiedzi pierwszego, wie, że ma zieloną. Jak nie – wie że ma czerwoną. Oczywiście przy każdej odpowiedzi „czerwona” wszystkie krasnoludki, które pozostały uaktualniają wiedzę (jeśli dotychczas oczekiwały liczby parzystej, to teraz będą nieparzystej i vice versa).

W tej strategii wszystkie krasnoludki poza pierwszym mają pewność przeżycia. A pierwszy też może przeżyć, jak będzie miał fuksa. Nie da się stworzyć takiej strategii, aby ten pierwszy miał pewność, zatem jest to strategia optymalna.

A co jeśli krasnoludków jest przeliczalnie wiele? (hint: wolno używać aksjomatu wyboru)

Hmmm. Nie mam pomysłu. Ale można ustalić, że tę strategię stosujemy dla n krasnoludków. A następne n krasnoludków zaczyna od nowa. Zginie wtedy 1 krasnoludek na 2n. Ponieważ n może być dowolnie duże, to w zasadzie można tę strategię optymalizować dowolnie dobrze.