Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
Ah, I love these kind of puzzles!<p>Here&#x27;s another one, similiar to the first one (Names in Boxes). Apologies for any incorrections in advance.<p>There are 100 prisoners. At random times one prisoner is chosen uniformly at random and led into a room with a single lamp. The prisoner can choose to switch it on or off or leave it as the last visiting prisoner left it. Apart from the state of the lamp he must leave the room unchanged.<p>After visiting the room, each prisoner is asked if every prisoner has visited the room by now. If he answers &#x27;Yes&#x27; and indeed everyone has been to the room at least once, then everybody is freed immediately. Otherwise they are all executed ;) He can answer &#x27;I don&#x27;t know&#x27; without any consequences.<p>Apart from the lamp being on or off the prisoners have no way of communication at all, but of course as is customary in such puzzles they can plot a strategy in advance and everybody is a perfect logician.<p>So, to clarify: The goal is for one prisoner to be 100% sure that everybody has been to the room at least once. The &quot;easiest&quot; solution would simply be to wait a few billion years (it&#x27;s an abstract puzzle, they are all immortal anyways ;). But of course there is a more elegant solution that terminates earlier.<p>Also, as the time for a visit is chosen at random a prisoner has no way of knowing who the previous person in the room was. It might just as well have been himself!<p>As there is some randomness involved, it is theoretically possible that the goal state never happens. Just assume that in the limit everybody will have visited the room infinitely often ;)<p>In other words: Implement synchronization between 100 threads with only one bit of shared memory and completely random scheduling.