About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
July 2002
Elect a spokesman.
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.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com