Prisoners Puzzle With A Twist

Should they really take the deal?

There is an old puzzle you may have heard of, which we will discuss a variation of. A group of mathematicians was sentenced to five years imprisonment for falsely claiming to have solved the Riemann Hypothesis. They are kept in solitary confinement most of the day, which is hardly cruel and unusual punishment given they have full access to the mathematics library and a whiteboard in every cell! But they would rather be able to discuss their findings with their colleagues over coffee.

A few days after their sentence begins, the warden, also a mathematician, called a meeting and made the following proposal: the mathematicians can decide to enter a contest in which the warden will select a prisoner randomly from solitary confinement every day and put him in a room. In the room is a single light switch, which will be in the off position the day the game begins. The selected prisoner can decide to turn the light on or off, but other than that, there is nothing to do in the room. The prisoner is not allowed to touch anything in the room or attempt to leave any kind of message. The other prisoners will not know who has been selected on any day and they will not be allowed to communicate in any way after the game begins. If one of the prisoners can correctly announce when all the mathematicians have been in the room at least once, the warden will free them all immediately. However, if they decide incorrectly, he will double their sentence to ten years. The warden gives the prisoners one hour to confer. Should the prisoners take the deal?

This is a two part puzzle: 1) Is there a way for the prisoners to infallibly decide whether all prisoners have been in the room at least once, even though they are not allowed to communicate? and 2) Should they take the deal even if they can figure out a solution to question 1? This puzzle as typically presented stops with question 1. Question 2 is more interesting. If it takes longer than five years to decide whether all prisoners have been in the room, it’s not worth it to take the deal.

See if you can solve these. The solution to the first question is here. The solution to the second puzzle is for more advanced students and can be found here.