The Eccentric Warden
Here's a puzzle I discovered recently, it was presented to me as a "Google Challenge", supposedly a question Google recruiters use to test the problem solving abilities of candidates.
Twenty prisoners are serving time in a backwater jail led by an eccentric warden. The warden has decided to play a game with the prisoners. He will lead the prisoners one at a time into a room with two switches. Each switch (the left and right one) may be in one of two states (ON or OFF). The prisoner must flip one and only one of the switches and then he is led back to his cell.
The warden decides in advance the methodology he is using to select which prisoner visits the room next. This methodology is kept a secret by the warden and the only guarantee is that if the game goes on forever, each prisoner will visit the room an infinite number of times.
The warden tells the prisoners these rules before the game begins, and says that any prisoner can stop the game before flipping a switch by declaring that all twenty prisoners have visited the room. If he is right, all the prisoners are set free, otherwise they are all executed!
All the prisoners are kept in isolation for the duration of the game and cannot communicate other than through using and observing the switches. However, before the game begins, the prisoners can meet to discuss their strategy. What should their strategy be?
Keep in mind that the warden may choose a methodology such as: "19 of the prisoners visit the room randomly until 10 years has elapsed. Afterwards, all 20 prisoners visit the room regularly." So it wouldn't be wise to use probability in your strategy, such as: "Well after 8 years, chances are we've all been to the room."
Twenty prisoners are serving time in a backwater jail led by an eccentric warden. The warden has decided to play a game with the prisoners. He will lead the prisoners one at a time into a room with two switches. Each switch (the left and right one) may be in one of two states (ON or OFF). The prisoner must flip one and only one of the switches and then he is led back to his cell.
The warden decides in advance the methodology he is using to select which prisoner visits the room next. This methodology is kept a secret by the warden and the only guarantee is that if the game goes on forever, each prisoner will visit the room an infinite number of times.
The warden tells the prisoners these rules before the game begins, and says that any prisoner can stop the game before flipping a switch by declaring that all twenty prisoners have visited the room. If he is right, all the prisoners are set free, otherwise they are all executed!
All the prisoners are kept in isolation for the duration of the game and cannot communicate other than through using and observing the switches. However, before the game begins, the prisoners can meet to discuss their strategy. What should their strategy be?
Keep in mind that the warden may choose a methodology such as: "19 of the prisoners visit the room randomly until 10 years has elapsed. Afterwards, all 20 prisoners visit the room regularly." So it wouldn't be wise to use probability in your strategy, such as: "Well after 8 years, chances are we've all been to the room."
posted by flowbeus at 2:59 PM
1 Comments:
WARNING! Below is the Solution, do not read unless you've given up.
I arrived at this solution myself, so I do not know if it is the intended solution, although it seems likely.
The 20 prisoners decide on one person to be the Counter, and the other 19 will be Flippers.
1) When a flipper enters the room, if the right switch is off, and the flipper has not yet had a chance to turn it on, he does so. Otherwise, he toggles the left switch.
2) When the counter enters the room, if the right switch is on, he will switch it off. Otherwise, he will toggle the left switch.
3) When the counter enters the room and observes the right switch on for the 19th time, he knows everyone has been to the room.
Note that in this solution, the right switch is assumed to begin in the off state. I have not solved the problem for the case where we don't know the starting state of the right switch.
Also note that this solution may take a very long time to work.
What I find interesting about this problem is that you can simplify it by saying there is only one switch and each prisoner has the option of flipping it or not. If you substitute "toggle the left switch" with "do nothing" in the strategy above you get the same result.
In the solution above, the left switch doesn't really serve a purpose, and I feel the version of the puzzle that has only one switch would be easier to solve since it prevents the contemplation of more complex strategies.
Post a Comment
<< Home