Code to evaluate a postfix expression
September 26, 2015
Find minimum and maximum value in a tree
January 5, 2016

Prisoners and the lightbulb puzzle

There are 10 prisoners are in 10 different cells of a prison. There is no way in which they can communicate with each other.
Each night, the warden picks one of the 10 prisoners and that prisoner is supposed to spend the entire night in the central living room. There is one bulb in the living room which can be switched on or off.
Warden puts a condition, “If any of the prisoner can tell with certainty, that all the other prisoners have spent night in the central living room, then he will free all of them. But, If the prisoner says that all the other have spent night in the living room, but that is not true, then all the prisoners will be killed”. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Before the random picking begins, the prisoners are allowed to get together and make some strategy. But, once the strategy is made, then a prisoner cannot communicate with any other prisoner.
What plan should they agree on, so that eventually, someone will make a correct assertion?
Solution:

From the problem it is clear that there is no limit on the number of times that a prisoner can go into the living room (because warden picks randomly), the problem is that they will not be able to communicate with each other that they have spent the night in the cell.

Therefore one person is chosen as the counter.

Every time any prisoner is selected other than counter person , he will follow these steps.

  1. If the bulb is already switched on then he will do nothing.
  2. If he has never switched on the bulb, and the bulb is off then he will switch on the bulb
  3. If he has switched on the bulb earlier, then he will do nothing (one prisoner will switch on the bulb only once).

If person who is made ‘counter’, goes to the living room, then,:

  1. If the bulb is on then he will increment the counter by one, and switch it off.
  2. If the bulb is already off then he will do nothing.

When the counter switch off the bulb 9 times, it will indicate that each of the other prisoner has already been to the living room at least once, because one prisoner is switching on the bulb only once. Hence at this time, the counter can declare that all the prisoners have spent the night in the cell.

 

4 Comments

  1. Clifford Kahn says:

    What if the lightbulb is on at the outset? The problem statement doesn’t say that the lightbulb starts out off.
    Suppose it is on at the outset. Suppose the counter is the first selected. Then by the algorithm, he/she could increment the count. But that would be incorrect, would it not?

    • Kamal Rawat says:

      You are right. That’s a miss. It can however be changed that on the very first day the person will just set it off or don’t do anything if it is already off.
      If you catch such things during the interview, then its a big plus.

      • Naresh says:

        Since prisoners can count the day they are sent in, the counter person will know that he is the first person and don’t increment the counter on day 1.

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *