Portál:Matematika/Odporúčaný článok/4 2016
Problém 100 väzňov je matematický problém z teórie pravdepodobnosti a kombinatoriky. Aby väzni prežili, musia všetci nájsť svoje vlastné číslo v jednom zo 100 zásuviek, pričom každý väzeň môže otvoriť iba 50 zásuviek a nemôže s ostatnými väzňami komunikovať. Na prvý pohľad vyzerá situácia beznádejná, ale existuje stratégia, ktorá dáva väzňom realistickú šancu na prežitie. Problém bol prvýkrát sformulovaný v roku 2003 dánskym informatikom Peter Bro Miltersenom.
Zadanie[upraviť zdroj]
Problém 100 väzňov bol rôzne formulovaný rôznymi autormi. Nasledujúca verzia je voľným prekladom zadania podľa Phillippe Flajoleta a Roberta Sedgewicka:
- Riaditeľ väznice sa rozhodne dať poslednú šancu svojim 100 väzňom odsúdeným na smrť. Do svojej kancelárie, kde má 100 zásuviek (označených číslami 1 – 100) náhodne umiestni kartičky s číslami väzňov, ktorí sú tiež označení číslami 1 – 100. Väzni majú po jednom vchádzať do kancelárie. Každému dovolí otvoriť najviac 50 zásuviek. Z miestnosti odchádzajú inou chodbou, nemajú ako podať ďalším čakajúcim väzňom informácie. Riaditeľ väznice sa rozhodol, že omilostí všetkých väzňov, ale iba (práve) vtedy, keď sa každému z väzňov podarí nájsť svoje číslo v jednej z 50 otvorených zásuviek. Ak čo len jeden z nich svoje číslo nenájde, všetci zomrú. Akú stratégiu majú väzni použiť, ak chcú mať čo najväčšiu šancu prežiť?