This one is super tough, so strap in!
There are 100 prisoners in solitary cells. There’s a central living room with one light bulb, which is initially off. No prisoner can see the light bulb from his or her own cell.
Every day, the warden picks a prisoner equally at random and takes them out to the central living room. While there, the prisoner can toggle the bulb on or off if they wish.
Also, the prisoner has the option of asserting the statement: “Every prisoner has been to the living room at least once.” If this assertion is false (i.e., some prisoners still haven’t been to the living room), all 100 prisoners will be shot for mutiny.
However, if it is indeed true, all prisoners are set free and inducted into MENSA, because they displayed immense intelligence.
The prisoners are allowed to get together one night, in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?
Rules:
- The light bulb is only accessible in the central living room.
- The prisoners cannot communicate with one another except for their one night to discuss a plan.
- The warden is not necessarily fair and might pick the same prisoner multiple days in a row. However, he does pick randomly.
The Challenge:
What is the strategy they should employ to ensure someone can make a correct assertion and free them all without risking their lives?
The prisoners designate one prisoner as the “counter.” Every time a prisoner who is not the “counter” goes to the living room and finds the light off, he turns it on but only the first time he himself has ever turned it on. If he has turned it on before, he does nothing.
When the “counter” goes into the living room and finds the light on, he turns it off and adds one to his mental count. The counter is the only person who turns the light off.
The Assertion
When the counter’s mental count reaches 99, he can confidently assert that all prisoners have visited the living room at least once.
The Explanation
- Every prisoner who is not the “counter” turns the light on exactly once, and only if they find it off.
- The counter is the only one who turns the light off, and he does so while keeping a count.
- By the time the counter has turned off the light 99 times, he knows for sure that 99 other prisoners have been to the room (not counting himself). At that point, it is safe to assert that every prisoner has been to the living room at least once.
The strategy ensures that all 100 prisoners will be set free and avoids the risk of a false assertion. It’s a clever use of minimal resources to solve a seemingly insurmountable problem!
Not easy, right?!
