Sto więźniów i pudełka

Na czym polega zagadka?

100 więźniów, każdy z numerem 1–100, musi znaleźć swój numer w jednym ze 100 pudełek — otwierając najwyżej 50 z nich. WSZYSCY muszą trafić, by przeżyć; po rozpoczęciu nie mogą się komunikować. Numery są rozmieszczone w pudełkach w ustalony (nieznany więźniom) sposób — to permutacja. Intuicja podpowiada, że sprawa jest beznadziejna.

Strategia losowa — praktycznie zero:

Gdyby każdy otwierał 50 pudełek na chybił trafił, szansa pojedynczego więźnia to $1/2$, a szansa wszystkich stu naraz:

To liczba tak mała, że praktycznie zerowa — mniej prawdopodobna niż trafienie w jeden konkretny atom we Wszechświecie.

Strategia cyklowa — genialny pomysł:

Każdy więzień zaczyna od pudełka o swoim numerze, sprawdza numer znaleziony w środku, przechodzi do pudełka o tym numerze i powtarza — „podąża za cyklem permutacji". Kluczowa obserwacja: rozmieszczenie numerów to permutacja, która rozkłada się na cykle. Więzień znajdzie swój numer w ≤ 50 krokach dokładnie wtedy, gdy cykl zawierający jego numer ma długość ≤ 50.

Dlaczego to działa? (niezmiennik)

Wszyscy odniosą sukces wtedy i tylko wtedy, gdy permutacja nie ma żadnego cyklu dłuższego niż 50. Prawdopodobieństwo tego dla losowej permutacji 100 elementów wynosi:

Aż ≈ 31%! Sprytna, skoordynowana strategia — mimo braku komunikacji — zamienia szanse z „praktycznie zero" na „prawie jedną trzecią". W naszej przykładowej permutacji najdłuższy cykl ma długość 47 (≤ 50), więc wszyscy przeżyją.

Historia zagadki

„Sto więźniów i pudełka" to jedna z najsłynniejszych i najbardziej zaskakujących zagadek matematycznych. Sformułowali ją i rozwiązali Anna Gál i Peter Bro Miltersen w 2003 roku. Zdumiewa właśnie dlatego, że wynik przeczy intuicji — trudno uwierzyć, że koordynacja bez komunikacji potrafi tak drastycznie podnieść szanse.

Po co Ci to na maturze:

To wzorcowy przykład, jak myślenie o strukturze problemu (tu: cyklach permutacji) bije naiwne liczenie. Rozszerza temat permutacji, ich cykli i prawdopodobieństwa — chwyt uniwersalny: zamiast liczyć „po ile możliwości", zapytaj, od czego dokładnie zależy sukces (tu: od długości najdłuższego cyklu).

Zapamiętaj: strategia losowa daje $(1/2)^{100}\approx 0$, a cyklowa aż $\approx 1-\ln 2 \approx 0{,}31$ — sukces wszystkich zachodzi dokładnie wtedy, gdy najdłuższy cykl permutacji ma długość ≤ 50.