Last Friday, The Riddler posed quite the challenging problem. Here it is in my own words.
You are in prison with 99 other inmates (there are 100 of you). The warden presents you with a game. Prisoners are to be randomly selected with replacement and taken into Cell Zero. Inside Cell Zero, there are two levers that could be in any of the following configurations:
Each prisoner that is let into Cell Zero can either declare “All prisoners have now been in Cell Zero” or move exactly one lever (and they must move exactly one lever).
If the prisoner declares and is wrong, all prisoners are executed.
If the prisoner declares and is correct, all prisoners go free.
Once the game has begun, there can be no communication between prisoners. What strategy at the outset will ensure that all prisoners go free?
Do the prisoners know the original configuration of the levers? NO.
Do we know which prisoner will be selected first? NO.
Can prisoners be selected multiple times before another prisoner has ever visited Cell Zero? YES.
I think I have a solution to this. It may not be the best, but here goes.
Since I have strong leadership skills among all the prisoners, I declare myself “the counter.” My job is to only move the left lever UP, and count each time I do it. If it is already in the up position, I just move the right lever down or up, regardless of its orientation.
All other prisoners’ job is to move the left lever DOWN exactly twice. Once they have moved the left lever from the UP position to the DOWN position twice, they forever will move only the right lever. If the left lever is already in the down position, they leave it be and move only the right lever.
Once I have counted to 198, I declare everyone has been in Cell Zero.
When I first visit Cell Zero and the left lever is down, I have no way of knowing whether it started that way or if another prisoner moved it down from the up position. So, when I move it up, I don’t know whether I’m starting at 0 or counting an actual prisoner.
Therefore, once I count to 99, I’m in a state of uncertainty. Have I counted all prisoners, or am I perhaps missing one? This uncertainty is just that, uncertainty. Since I cannot be certain, we should devise a different strategy.
By having all the prisoners pull the left lever down exactly twice, then I will eventually lift the left lever up 198 times. There is still now an uncertain state, and that is whether all prisoners have pulled the left lever down twice (a prisoner visited Cell Zero the first time before me with the left lever up and pulled it down), or there is still one out there that hasn’t pulled it down a second time yet (the left lever started in the down position). But that gives us the level of certainty that we need: that all the prisoners have been in Cell Zero at least once.