Fejtörő: Adott egy börtön, melyben a cellák hermetikusan elzártak, a cellák közt semmilyen kommunikáció nem lehetséges

Adott egy börtön, melyben a cellák hermetikusan elzártak, a cellák közt semmilyen kommunikáció nem lehetséges. Bekerül a börtönbe x db rab. A rabok együtt érkeznek és ismerik a börtön adottságait. A börtönőrök viszik sétálni a rabokat, naponta akár többet is, de teljes véletlenszerűséggel.

Egy nap akár egy rabot többsör is levisznek, de lehet olyan rab aki akár egy hónapig, vagy tovább nem sétál. Egyszerre egy rab sétál. Az udvaron van egy kapcsoló, melynek két állása van, A és B (a kapcsoló eredetileg az A állásban van). A rabok ezzel a kapcsolóval kommunikálhatnak: a séta alatt átkapcsolhatják. A börtönőrök nem nyúlnak a kapcsolóhoz. A rabok akkor szabadulnak ki, ha valamelyik rab kijeleni, hogy: “Már minden rab volt legalább egyszer sétálni!” és a kijelentés IGAZ. Ha a kijelentés nem igaz, soha többé nem szabadulnak ki. Tehát csak egyszer lehet ilyen kijelentést tenni. Hogyan szabadulhatnak ki?

Megoldás:

Ha egy rab még nem nyúlt a kapcsolóhoz, és az A állapotban van, akkor átbillenti B-be. Van egy kitüntetett rab, akinek az a feladata, hogy ahányszor kimegy, ha a kapcsoló B állapotban van, akkor visszaállítja A-ra és növeli a számlálót eggyel. Ha a számláló elérte az (x-1)-et, akkor tudja, hogy a rajta kívül állók mindegyike volt már egyszer kint, ő is volt, tehát megteheti a kijelentést.