The light bulb room

Chance and uncertaintyLevel 4 · Advanced · ●●●●○

There are 100 prisoners. Each day, the guard chooses one at random and takes it to a room with a light bulb (with on/off switch).

The prisoner can flip the switch or not. Then he returns to his cell.

They don't know when they will be elected again. At any time, a prisoner can declare: 'We've all been in the room at least once.' If it's true, everyone is free.

If it's false, everyone dies. At first the light bulb is off.

What strategy guarantees freedom?

Solve this riddle

Hints

Show hints

Protocol: If you ever walk in and see the light off for the first time, turn it on.
Protocol: every time you enter and see the light on, turn it off and add 1.
Single counter strategy.

Solution

Show full solution

Answer: Single counter strategy.
Light-bulb counter room: minimal counter/non-counter protocol
Protocol:

A single accountant is designated.
Each non-counter:

if you ever come in and see the light off for the first time, you turn it on;
Afterwards, he never touches her again.

The counter:

every time he enters and sees the light on, he turns it off and adds 1;
upon reaching 99, declare that everyone has passed.

Why this is correct:

Each non-counter contributes at most one "token" (one lit).
The counter records exactly those tokens when turned off.
Counting 99 tokens implies that the other 99 have already visited the room.

The strategy guarantees success, although the expected time can be very high under random selection.

Related riddles

Keep practicing

If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.

← Previous: The hundred prisoners with hats · Next: The twenty five horses →