The Hardest Prisoner Problem Ever (Part 1)
There are 6 prisoners and the warden decides to play the following game.
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)
The answer is 5.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
One Counter strategy--
Appoint one of the prisoners as the Counter. Everyone knows the initial state of switch is "off".
The rule for each prisoner who is not the Counter is this ---
If the switch is in the OFF position and the prisoner has never switched it ON before, then he must flip it ON. He will only do this once. If he has flipped the switch before, he won't do anything.
If the switch is in ON position, he does nothing.
The rule for the Counter is ---
If the switch is OFF, he will do nothing
If the switch is ON, he will switch it OFF and add one to his count.
When the Counter flips switch OFF 5 times, (once for every prisoner other than himself) he knows every prisoner has visited at least once and pushes the button.