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.
Your Answer
More puzzles to try-
Coke Riddle
Jacob has 25 dollars, he spends 20 dollars on a Coke. What does he have?Read More »Charades Riddle
These types of puzzles are known as charades. What you have to do is to find two words that are ...Read More »What is it?
No matter how much rain comes down on it it won’t get any wetter. What is it?Read More »Help to Cross Bridge
A bridge is about to collapse. There are four people P, Q, R and S on one of the sides. ...Read More »Servant and ruler riddle
What when read from right to left is a servant but when read from left to right is a ruler?Read More »Death in a Field
A man is lying dead in a field. Next to him there is an unopened package. There is no other ...Read More »Barber selecting brain teaser
There are only two barbers in the town. One of them has a nice, neatly trimmed head of hair. The ...Read More »How many words
How many words can a pen with half refill write?Read More »A Farmer, a Wolf, A Goat, and a Cabbage
A farmer went to a market and bought a wolf, a goat, and a cabbage. On his way home, the ...Read More »Foot size and spelling test riddle
scientific studies have shown that there is a direct, positive correlation between foot size and performance in spelling tests. how ...Read More »Song wins $1,000 riddle
A poor woman and a rich woman are talking about music. The poor woman says she has studied music and ...Read More »Man pushes his car and stops in front of a hotel puzzle
A man pushes his car and stops in front of a hotel and immediately goes bankrupt. What is he doing?Read More »6 Teacher and theif puzzle
6 Teachers were going to school altogether. A chain snatcher steals a chain Telugu teacher – Donga Donga, Eng teacher ...Read More »Bankrupt declared riddle
A man takes his car to a hotel. Upon reaching the hotel, he is immediately declared bankrupt. Why?Read More »Coin on table riddle
You are sitting with one opponent at an empty, round table. Taking turns, you should place one euro on the ...Read More »Making Traingles
Make 4 triangles by moving the position of only one pencil.Read More »Connecting 9 dots with 4 line puzzle
Look at the 9 dots in this image. Can you draw 4 straight lines, without picking up your pen, that ...Read More »Reach the Island logic puzzle
Alexandra wants to reach an island which is in the middle of the river. The island is 30 feet from ...Read More »Number is upside down
What year of this century is the same when its number is upside down? What year of the previous century ...Read More »Three boys in the field
Three boys are walking across a green and luscious field. Only two of them are wearing rubber boots and yet ...Read More »