One hundred people cannot communicate with each other. Their only link to the outside is a light bulb that they can find on or off. The difficulty is that no one knows what state they are in when they start.
The light-bulb room
Riddle statement
There are 100 prisoners. Before you start, you can agree on a strategy. Then, each day, the guard chooses one and takes him to a room with a light bulb, which can be on or off. The prisoners do not know the initial state of the light bulb.
Each prisoner can enter many times. On each visit you can leave the bulb as it is or change its status. When leaving, you cannot communicate with others.
At any time, anyone can declare: “We have all been through the room at least once.” If he is right, everyone is free; If you make a mistake, everyone dies.
What strategy allows you to declare with certainty that everyone has passed through the room?
Show solution
Solution
Answer: they appoint an accountant. Each of the other 99 prisoners sends exactly two signals: they turn on the light bulb when they find it off, until they have done so twice in total. The counter turns off the light bulb every time it is on and keeps track. When it reaches 198, he declares that everyone has passed.
The strategy in detail:
Before starting, they designate a prisoner as counter.
Each non-counter keeps his own count of signals sent, initially at zero.
If a non-counter enters, sees the light bulb off and has sent less than two signals, he turns it on and adds one to your account.
If you have already sent your two signals, you do not touch the light bulb.
If you enter and the light bulb is on, you do nothing.
The counter, every time you enter and find the light bulb on, turns it off and adds 1 to your internal count.
When the counter reaches 198, it declares that everyone has passed through the room.
Why does it work?
There are 99 prisoners who are not the counter, and each one can contribute a maximum of two signals:
The only risk is that the light bulb was on at the beginning: in that case, the counter would register a false signal at the beginning, counting something that no prisoner turned on. It must be shown that even then, reaching 198 guarantees that everyone has passed.
Suppose that some non-counter has never entered the room. The remaining 98 can contribute a maximum of:
real signals. Adding the possible initial false signal, the counter could reach at most 197. It cannot reach 198.
Therefore, if the counter reaches 198, all non-counters have passed at least once. And the accountant has also passed, since he himself has entered to count. The statement is certain.