Fog Creek Software
Discussion Board




New switches puzzle

Twenty three prisoners arrived at a prison whose warden was renowned for his mercy.  On arrival, they were told that the warden was going to meet them immediately.  The warden, however, did not show up.  So the prisoners were brought to their cells.

At night, one of the prisoners found in his bed a hidden piece of paper, which reads:

"Shit, we are misinformed. There are three switches, not two. One on the left of each door in the rotating tower ... Hope the buddies are smart enough.  Forgive me, Arwen my love.  I probably can't see you again."

Next day, the absent-minded Warden Spolsky met all the prisoners and told them how merciful he was.  For the details, see

http://www.techinterview.org/Puzzles/twoswitches.html

How could all the prisoners get freed?

Hankel O'Fung
Friday, February 27, 2004

Just to clarify, are you saying that there are three switches in a room with three doors, and since the tower is rotating, prisoners cannot tell which switch is which?

Or are there three *pairs* of switches, and the prisoners are each taken to one of the pairs without knowing which is which?

Ham Fisted
Tuesday, March 02, 2004

I meant the former one, i.e. there are three indistinguishable switches in a rotating room.  This variant of the puzzle should be easier than the original one.  Have fun!

Hankel O'Fung
Wednesday, March 03, 2004

In the orginal two switches puzzle, the solution contains:

1. A prisoner who is the counter
2. Switch states which signals the counter to increase count
3. A toggle method for prisoners who has already sent signal
4. Some compensation for the unknown initial switch state

In light of above observation, one could mimic the pattern and come up with a particular solution to the "New switches puzzle."

Again we will have a prisoner who is the counter.

Let the switch state of "all switches on" to be the signal for the counter to increase count.  Call this state the signal state.

Prisoners other than the counter will each keep a variable S that stands for the number of times to send the signal.  Initially S = 2 for all prisoners (except the counter, counter doesn't need to send a signal to self).  When a prisoner sends a signal, i.e. change the switches to the signal state, the prisoner will decrease S by one.

If a prisoner enters the room and S = 0, then the prisoner needs to toggle.  If a prisoner needs to toggle, there are two cases.

Case one:
When the prisoner enters the room, the switches are not in the signal state, then the prisoner will toggle a switch such that the switches are not changed to the signal state.

Case two:
When the prisoner enters the room, the switches are in the signal state, then the prisoner is forced to change the switches to a non-signal state.  In this case, the prisoner will increase S by 1.

If the counter enters the room and see a signal state, then increase count by one, change signal state to non-signal state.  If the counter enters the room and see a non-signal state, then just toggle to another non-signal state.

When the count reaches 44, all prisoners have visited the room.

JHY
Thursday, March 04, 2004

sir,
I was enjoying ur puzzles.Iwant the solution for the original switches problem.I was not able to solve that problem.

venkat reddy
Tuesday, March 16, 2004

Solution to original switches puzzle, copy and paste link if necessary.

http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/July2002.html


Also, there had been many threads discussing this puzzle, check out some of them at the links below.  Remember that they are only discussions and many of them have flawed solutions.

http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=1704

http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=1501

http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=1307

http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=1206

http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=1115

JHY
Tuesday, March 16, 2004

*  Recent Topics

*  Fog Creek Home