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 »
- There are 10 stacks of 10 coins each. Each coin weights 10 gms. However, one stack of coins is defective ...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 »
- Paul, Sam and Dean are assigned the task of figuring out two numbers. They get the following information: Both numbers ...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 »
- A devotee goes to three temples, temple1, temple2 and temple3 one after the other. In front of each temple, there ...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 »
- Two trains starting at same time, one from Bangalore to Mysore and other in opposite direction arrive at their destination ...Read More »
- Let it be simple and as direct as possible. Interviewer : Tell me how much time (in days) and money would ...Read More »
- Solve this logic sequence puzzle by the correct digit- 8080 = 6 1357 = 0 2022 = 1 1999 = ...Read More »
- A man leaves his house in the morning to go to office and kisses his wife. In the evening on ...Read More »
- Jasmine, Thibault, and Noah were having a night out and decided to order a pizza for $10. It turned out ...Read More »
- Which letter replaces the question markRead More »
- A murderer is condemned to death. He has to choose between three rooms. The first is full of raging fires, ...Read More »
- Richie established a very strange number system. According to her claim for different combination of 0 and 2 you will ...Read More »
- The result of math class test came out. Fariha’s mark was an even number. Srabon got a prime!! Nabila got ...Read More »
- Robi is a very serious student. On the first day of this year his seriousness for study was 1 hour. ...Read More »
- Ragib: I got digits of a 2 digit number Sakib: Is it an odd? Ragib: Yes. Moreover, the sum of ...Read More »