23 Prisoners

3.5 stars

A warden meets with the 23 prisoners when they arrive at the prison.

He tells them:

You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.

There is in this prison a "switch room" which contains two light switches, labelled "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". This prisoner must 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. Apart from these prisoner visits no one will ever enter the "switch room".

At any time, any one of you may declare to me, "We have all visited the switch room." If it is true (ie. 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 a strategy which will guarantee the prisoners' release.

 


Answer:

All the prisoners get together and nominate a "leader".  The leader is going to count how many different prisoners have visited the switch room. When the count equals the number of prisoners, he goes to the warden and says "all the prisoners have visited", and everyone goes free.  Here's the strategy for the leader and the followers:

Visit by a follower:

  • If switch A is on, toggle switch B.
  • If switch A is off and you have not previously toggled switch A, and you have previously seen switch A on, toggle it on, otherwise toggle switch B.
  • If switch A is off and you have previously toggled switch A, toggle switch B.

Visit by the leader:

  • If switch A is off, toggle it on. 
  • If switch A is on, toggle it off.  If you did not turn switch A on during your previous visit, increment the count of prisoners.

Each follower must remember two things, 1) whether they've seen switch A on during any previous visit, and 2) whether they've previously toggled switch A.  They must have seen switch A on before toggling it on themselves, and they will only toggle it on once.  

The leader must remember two things also, 1) whether he toggled switch A on during his previous visit, and 2) the current count of followers who have toggled switch A.

Solution submitted by reader who found it here www.w-uh.com/posts/030530-the_two_switches.html

 

Difficulty
  • Hard
Type
  • Logic
Submit your vote:

    

Comments

tell me the way how will leader count
- abhinav (31 Jul 2014)

the answer still doesn't guarantee freedom for the prisoners, because the leader is not guaranteed to go first, and they can't choose the leader based on who's going to go first because they don't know who's going to go first. If the Leader doesn't go first and the A switch is off then the first person will turn it on, and the leader will not know whether the A switch has been turned on or not. If this is the case, in the end the leader will only count 21 people have switched the A switch, he will never know for certain whether the person who isn't counted yet hasn't gone to the switch room yet or that he had gone first. And let me add that the probability that somebody other than the leader goes to the switch room first is 22/23 while the chance that the leader actually goes first is only 1/23. the chance of A switch being off when the game started is 1/2
- (5 May 2015)

What does toggle mean?

Is toggle the button or what?

Thanks in advance to anyone who replies to this! I will reply ASAP :)
- Ruby Redfort xD (11 Apr 2016)

Post your own comment

Name:
URL:
Anti-spam check
To prove you are human, what traffic light color means stop?(Hint: 3 letters, beginning with R)
Comments:
Note: comments may be edited and will not appear until approved