Solution to First Prisoners Puzzle Question

Yes, it can be done!

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?

Solution

Here’s how to win the game with certainty. The prisoners appoint one mathematician, Bob, to be the official counter. Bob’s only job is to add one to his count every day he is randomly selected to enter the room, and he sees the light switch turned on. He then must turn the switch off. If he is selected to enter the room when the light switch is turned off, he does nothing.

Every other prisoner’s only job is to switch the light on the first time he is randomly selected to enter the room, but only if the light switch is not already on. In all other cases, the prisoners must do nothing when they are randomly selected to enter the room.

In this way, every prisoner turns on the light exactly once and Bob counts that prisoner when he is randomly selected to enter the room. When Bob counts N-1 light switches that have been turned on, he can be sure that all N prisoners, including himself, have been in the room at least once.