A certain number of people are put in a jail. Before they are taken to their
solitary cells, their jailers explain that each day one of them will be taken
into a room that contains a lightbulb that can be switched on or off, and will
be allowed to change its position if they want to do so. The prisoners are
allowed to nominate one of them as their leader. The leader (who will also be
taken to the lightbulb room, on equal footing with the rest) is allowed to
declare at some point that all prisoners have been to the switch room. If he is
right, the prisoners will be set free. If he is wrong, they will remain in jail
forever.
There is a guarantee that any finite sequence of prisoners being chosen to
enter the lightbulb room (e.g., prisoner #3, then #3, then #1, etc.) will
eventually be observed. Before the prisoners are separated, the prisoners can
discuss the matter and choose their leader and the strategy that may allow them
to go free one day. What should this be?