Sapkás rabok összevissza című feladványunkban a börtönőrök tíz rabot állítanak egymás után sorba. A rabok mindegyike véletlenszerűen néz előre vagy hátra (egyforma 50%-os valószínűségekkel), és mindenkinek a fejére egy színes sapkát tesznek, amely véletlenszerűen vagy kék, vagy piros. Senki nem látja saját sapkájának a színét, mindenki csak az előtte lévő többi rab sapkáit látja. Ha meg tudják tippelni saját sapkájuk színét, szabadon engedik őket. Milyen stratégiát kövessenek, és hány rab menekülhet meg biztosan?

Tegyük fel, hogy amikor a rabok már a sorban állnak (véletlenszerűen előre vagy hátra nézve), de még mielőtt a sapkákat megkapják, meg kell beszélniük, hogy milyen sorrendben tippelnek majd. A megbeszélés alatt forgathatják a fejüket. Miután megkapják a sapkákat, a megbeszélt sorrendben tippelhetnek saját sapkájuk színére. A sorrend nem függhet a látottaktól, annak az előre megbeszélt fix sorrendnek kell lennie. A tippeket mindenki hallja, és mivel megbeszélték a sorrendet, ezért pontosan tudják, hogy éppen kinek a tippje hangzik el (és az illető hányadik a sorban). Semmilyen más kommunikáció nem megengedett a nyilvános tippeken kívül. Amikor mindenki tippelt, elengedik azokat, akik helyesen tippeltek. Nyilvánvaló, hogy az első rab, aki tippel, nem tud biztosan megmenekülni, mert nem ismeri a sapkájának a színét, és semmilyen plusz információ nem áll a rendelkezésére. Előfordulhat azonban az, hogy a rabokat olyan módon állították sorba, hogy az első rab kivételével az összes többi meg tud menekülni, ha jó stratégiát választanak. A kérdés az, hogy mekkora a valószínűsége egy ilyen sorbaállításnak.

Milyen a jó sorrend?

Ha mindenki azonos irányba néz, az egy klasszikus feladvány, amivel biztosan sokan találkoztak már. A színekhez érdemes 0 és 1 számokat hozzárendelni. A tippelést a leghátsó rabtól kezdjük, aki magán kívül mindenkit lát. Ő adja össze az összes előtte lévő számot, és mondjon 0-át, azaz a 0-nak megfelelő színt, ha az összeg páros, és 1-et, ha az összeg páratlan. Ezután a rabok haladjanak előrefelé a tippeléssel. A leghátsó előtti rab mindenkit lát, akit a leghátsó látott, csak magát nem, így ki tudja számítani, hogy milyen sapka van a fején. Ha például az előtte lévő összeg páros, és a hátsó páratlant mondott, akkor rajta csakis 1-es sapka lehet. Miután bemondja a tippjét, ami helyes, az előtte lévő rab ezt ki tudja vonni a leghátsó által bemondott összegből, látja továbbá ő is az előtte lévőket, így teljesen hasonló módon ki tudja számolni ő is a sapkája színét, amit bemondhat, és így tovább.

Ehhez a módszerhez hasonló módszer működik akkor is, ha a csoport egyik fele áll szemben a másikkal, azaz mindenki a sor egy közbülső pontja fele néz:

Ekkor a sor egyik végén álló rabbal kezdve ugyanúgy megy a megoldás, mint korábban, mintha mindenki azonos irányba nézne. Amikor eljutnak az alakzat közepéig, ahol váltás van, a sor másik végén álló rab folytatja, hiszen ő saját magán kívül mindenkit lát, akit a túloldaliak láttak.

A kérdés az, hogy vajon más esetben is meg lehet-e menteni egy kivételével minden rabot. Minden más eset jellemezhető úgy, hogy van két egymás melletti rab a sorban, akik egymásnak háttal állnak. Azt állítjuk, hogy ilyenkor egy rab kivételével nem lehet mindenkit biztosan megmenteni. Ha kettejük közül kezd valaki, akkor ez nyilvánvaló, mert az első megszólaló után mindenkinek a saját sapkája színét kell mondania, és mivel egymást nem látják, semmilyen módon nem tudnak egymásnak segíteni, tehát van rá esély, hogy a másik rosszul fog tippelni. Ha más sorrendben haladnának, akkor mindkettőjüknek jól kellene tippelnie, és most igaz lesz, hogy amikor kettejük közül az első megszólal, akkor a tippje nem függhet a másik sapkájának a színétől, és ilyen módon semmilyen plusz információval nem szolgálhat számára. Ennek átgondolását a kedves olvasóra bízzuk.

Azt kapjuk tehát, hogy tizenegy olyan eset van, amikor egy kivételével minden rab biztosan meg tud menekülni: két eset, amikor azonos irányba néz mindenki, és kilenc eset (hiszen kilenc helyre szúrhatjuk be a szétválasztást), amikor szembenéz egymással két csoport. Az összes lehetséges sorrend pedig 2^10 = 1024, tehát a keresett valószínűség 11/1024, ami kb. 1%.

Kapcsolódó cikk a Qubiten: