technology and zen of life

“A heisenbug (named after the Heisenberg Uncertainty Principle) is a computer bug that disappears or alters its characteristics when an attempt is made to study it.”

Puzzle 4: The Two Switches

The warden meets with 23 new prisoners when they arrive. He tells them, “You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

“In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the ‘on’ or the ‘off’ position. I am not telling you their present positions. The switches are not connected to anything.

“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 will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can’t move both but he can’t move none either. Then he’ll be led back to his cell.

“No one else will enter the switch room until I lead the next prisoner there, and he’ll be instructed to do the same thing. I’m going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

“But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, ‘we have all visited the switch room’ and be 100% sure.

“If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators.”

Mail your answers to gurus [dot] comments [at] gmail [dot] com

Also comment if you have mailed the answer.

—————————————————————————————-

This problem is taken from a site which I will put up later, so that you don’t ruin the problem by looking at answer. Till then you brainstorm. It’s an awesome problem.

Leave a Reply

6 Responses

  1. Rod Paris says:

    There are 4 possible combinations, UU DD UD and DU.

    These can be changed as follows

    UU to UD or DU
    DD to UD or DU
    UD to DD or UU
    DU to DD or UU

    The prisoners agree beforehand that if this is their first visit, they leave the switches in, say, DD or DU positions. If this is a subsequent visit, they leave them in UU or UD positions.

    They each count how many times they find the switches in DD or DU positions, indicating that the person before them was on a first visit.

    The first prisoner to reach a count of 23 (including himself) hollers “Freedom for All”.

    Incidentally, you do need the sentence “…everyone will visit the switch room as many times as everyone else” to prevent the situation where one prisoner is only sent in a small number of times and his visit is not caught by the person after him that eventually reaches the 23 tally (think about it!).

  2. Owing to the random selection element, there will never be a highly efficient answer to the puzzle, as it will often result in repeat visits and hence wastage. The first prisoner remembers two things at all times: a running count and a switch state. Every time the first prisoner visits the cell, he arbitrarily flips Switch 1 (only because he has to), then if the state of Switch 2 is different to his previous visit, he increases his running count by one. Every time one of the other prisoners visits the cell, if they have not visited before, they flip Switch 2, otherwise they flip Switch 1. When the first prisoner’s running count equals the number of prisoners, he can confidently declare that everyone has visited.

  3. Will says:

    The prisoner is selected at random, the only rule is that after a time, all will have been selected equally as often as each other. There is no rule on how many times in a row etc…

  4. DarK says:

    3 times
    “I may choose the same guy three times in a row”

  5. Swistak says:

    may he choose same prisoner two times, or four?

    or is it 1 > 1 >1 >2 >3 >1 >1 >2 >3 ?

Email Subscription

Disclaimer

The views expressed on this blog are personal. We do not claim to be a representative voice of the views of any organisation whatsoever. We are not responsible for the content present on the blogs to which we have linked.Views expressed are solely that of the author and does not reflect a collective opinion of contributors.
%d bloggers like this: