Saturday, October 22, 2011
100 Prisoners and a Lightbulb
There are 100 prisoners in a jail, each in an isolated cell. In the lobby of the jail is a room with a light and a lightbulb (starts in the off position), which can only been seen from the lobby. Each day, the warden will take 1 random prisoner down to the lobby. The prisoner can flip the switch (either turning the bulb off it was on or on if it was off), or the prisoner can do nothing, or the prisoner can say "each prisoner has been to the lobby at least once." If the prisoner who says this is correct, they all go free. If he is incorrect, they are all killed. The prisoners can get together at the very beginning to discuss a strategy, but can not communicate with one another ever again until the exercise is over. What strategy can the prisoners use to guarantee that they all survive?
Subscribe to:
Post Comments (Atom)
1 comment:
The first prisoner taken is the only prisoner who can ever turn the light on. His job is to turn the light on every time he comes into the room and it is off. The rest of the prisoners will:
1) Turn the light off it is on and the prisoner has not turned the light off before
2) Do nothing if the light is already off
3) Do nothing if they have already turned the light off before
This way, the first prisoner will just have to count the number of times he has to turn the light on. Once he reaches 100, he can say all prisoners have been in the lobby at least once
Post a Comment