A prison jailor meets with the twenty three convicts when they arrive at the prison. He tells them:
You may meet today to discuss and plan a strategy, but after today you will be locked in isolated cells and have no communication with one another.
There is in this prison a "switch room" which contains two light switches, labeled "A" and "B", each of which can be in the "on" or "off" position. I am not telling you their present positions. The switches are not connected to any appliance. After today, from time to time, whenever I feel so inclined, I will select one prisoner at random and escort him to the "switch room", and this prisoner will select one of the two switches and reverse its position (e.g. if it was "on", he will turn it "off"); the prisoner will then be led back to his cell. Nobody else will ever enter the "switch room".
Each prisoner will visit the switch room arbitrarily often. That is, for any N it is true that eventually each of you will visit the switch room at least N times.)
At any time, any of you may declare to me: "We have all visited the switch room." If it is true (each of the 23 prisoners has visited the switch room at least once), then you will all be set free. If it is false (someone has not yet visited the switch room), you will all remain here forever, with no chance of parole.
Devise for the prisoners a strategy which will guarantee their release.
Answer will be posted tomorrow. If you are impaitent then search google..
ReplyDeleteHere is the answer..
ReplyDeletePrisoners need to elect a spokesman first.
Each prisoner other than the spokesman maintains a counter with initial value 0. When he enters the switch room, if switch "A" is "off" and his counter is 0 or 1, then he switches "A" to "on" and increments his counter. Otherwise (switch "A" is already "on" or his counter is 2) he switches "B".
The spokesman also has a counter with initial value 0. When he enters the switch room, if switch "A" is "on", he switches "A" to "off" and increments his counter. Otherwise (switch "A" is already "off") he switches "B". When the spokesman's counter reaches 44, he declares to the warden "We have all visited the switch room."
He is safe in making this declaration: among the 44 times that the switch had been "on", at most once was because the switch might have started out in the "on" position at the beginning of time. At most two were due to each prisoner (other than the spokesman himself) turning it on. If not everyone had visited the switch room, then it could have been turned "on" at most 2*21=42 times, and his counter would not exceed 42+1=43.
Further, given enough time, each prisoner will have two opportunities to turn "on" the switch, so that the spokesman's counter will eventually reach or exceed 44.
Switch "B" is only used so that the prisoner has something to flip when the protocol says he should not flip switch "A".
The non-spokeman prisoners turn the switch on twice instead of just once, because of the uncertainty about its initial position.