The Hardest Prisoner Problem Ever (Part 1)
The prisoners will be taken in random order (with replacement) into a room with nothing but a (two-state) light-switch and a button. Initially, the light-switch is in the off state. Each prisoner may do whatever he wants with the light switch. Prisoners will continue to be randomly taken into the room until one prisoner becomes certain that every single prisoner has been in the room at least once. At this point he may push the button and all of the prisoners will be set free.
No communication between the prisoners is possible once the game has begun. The prisoners must make a plan beforehand about how to use the switch to ensure that at some point during this process one prisoner will know that all of the prisoners have been in the room.
What strategy should they use? Assuming that the prisoners use the most efficient possible strategy, how many times at least will the light switch be switched on?
Once you solve this problem, try The Hardest Prisoner Problem Ever (Part 2)