The prisoners and the switch
N prisoners get together to decide on a strategy. Then, each prisoner is taken to his own isolated cell. A prison guard goes to a cell and takes its prisoner to a room where there is a switch. The switch can either be up or down. The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch. The prisoner is then taken back to his cell. The prison guard repeats this process infinitely often, each time choosing fairly among the prisoners. That is, the prison guard will choose each prisoner infinitely often.
At any time, any prisoner can exclaim “Now, every prisoner has been in the room with the switch”. If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed. What strategy should the prisoners use to ensure their eventual freedom?
(Just in case there’s any confusion: The initial state of the switch is unknown to the prisoners. The state of the switch is changed only by the prisoners.)
As a warm-up, you may consider the same problem but with a known initial state of the switch.
Reserve one prisoner with a special assignment (I’ll call her Sam). Each prisoner will turn on the light once, and only once, sending a signal to Sam. When Sam receives it, he notes that a signal has been received, and turns the light off. Once 99 signals are received, Sam knows that everybody has been in the room. Thus the instructions for each prisoner are:
- If you enter the room with the light off, and you have never turned it on, then turn it on.
- Otherwise, leave it.
More puzzles to try-
- 3 + 3 = 3 5 + 4 = 4 1 + 0 = 3 2 + 3 = 4 ...Read More »
- Which letter replaces the question markRead More »
- There is a building of 100 floors -If an egg drops from the Nth floor or above it will break. ...Read More »
- Five puzzleFry ship’s pirates have obtained 100 gold coins and have to divide up the loot. The pirates are all ...Read More »
- There are 10 stacks of 10 coins each. Each coin weights 10 gms. However, one stack of coins is defective ...Read More »
- Dr.Willam wants to operate for three different persons who were wounded. But he had only two surgical gloves. There is ...Read More »
- Which clock works best? The one that loses a minute a day or the one that doesn’t work at all?Read More »
- In the gear arrangement, To which one will the needle touch, 1 OR 2Read More »
- A man leaves his house in the morning to go to office and kisses his wife. In the evening on ...Read More »
- A murderer is condemned to death. He has to choose between three rooms. The first is full of raging fires, ...Read More »
- A bridge will collapse in 17 minutes. 4 people want to cross it before it will collapse. It is a ...Read More »
- In a country where everyone wants a boy, each family continues having babies till they have a boy. After some ...Read More »
- A devotee goes to three temples, temple1, temple2 and temple3 one after the other. In front of each temple, there ...Read More »
- There is a perfectly accurate analog watch with hour, minute, and second hands. How many times a day do all three ...Read More »
- Four days are there which start with the letter ‘T‘. I can remember only two of them as “Tuesday , Thursday”. ...Read More »
- Two fathers took their sons to a fruit stall. Each man and son bought an apple, But when they returned ...Read More »
- A farmer is taking her eggs to the market in a cart, but she hits a pothole, which knocks over ...Read More »
- Let it be simple and as direct as possible. Interviewer : Tell me how much time (in days) and money would ...Read More »
- In the middle of the confounded desert, there is the lost city of “Ash”. To reach it, you will have ...Read More »
- Solve this logic sequence puzzle by the correct digit- 8080 = 6 1357 = 0 2022 = 1 1999 = ...Read More »