A prisoner riddle
Quite some time ago, I came across a riddle, and I’d like to share a variant of it with you:
100 prisoners are incarcerated in a very peculiar jail. The jail has a single room with a light controlled by a switch that is initially off. The prisoners are each told that they will be taken one at a time into this room, and will be allowed to flip the switch if they so desire. They will then be taken back to their room, and another prisoner will be brought to the room, given the same privilege, etc. While there is no specific reasoning whatsoever to the order in which the prisoners are sent to the room, there is only one known fact: the order doesn’t forbid any prisoner from entering the room after some time. That is, if the order were to continue indefinitely, no prisoner would enter the room for his or her last time (this happens almost surely anyway). If any one prisoner at any time correctly claims that every prisoner has been to the room at least once (by shouting “DONE!”), then all the prisoners are set free. If he or she is wrong, they all are killed. Before the prisoners begin to be led into the room, they are allotted a single planning session in order to discuss a strategy. Is there a certain escape strategy for the prisoners?
If you like riddles, think about this one for a while before reading ahead. Keep in mind that the exact time of unanimous entry need not be known, but when a prisoner shouts “DONE!” each prisoner must have visited the room at least once, 100% of the time, always. If you get bored with this one, try to solve the problem assuming you do not know the initial condition of the switch.
