You are the janitor at a prison with 100 prisoners locked in separate, soundproof and windowless cells.
You watch one day as the warden brings the prisoners out to a central room where there are 100 boxes laid out, labeled 1 through 100. He hands each prisoner a slip of paper and a pen, and asks everyone to write their name on their slip and hand it back to him. All the prisoner's have different names.
The warden then makes a proposition to the prisoners. He will put them back in their cells and will put each of the 100 slips of paper into a different box. The prisoners will then be brought out one by one in a random order. When a prisoner comes out, he will get to open 50 boxes. He doesn't need to preselect which boxes he'll open; he can choose as he goes along. He is also not allowed to rearrange the boxes or the names as he does this.
If any of the 50 boxes he opens contains the slip with that prisoner's name on it, then that prisoner "passes" the test. He will be sent back to his cell, all of the boxes will be closed, and the next prisoner will be brought out. However, if any prisoner opens 50 boxes and none of them contain his name, then all 100 prisoners will be executed. Note that prisoners have no way of passing information on to any of the prisoners who go after them.
If all of the prisoners are able to "pass" the test, then they will all be set free, and you'll receive a big promotion.
Luckily for the prisoners, the warden is going to let you help them in the following way. After he's put all of the names in the boxes, he will bring you into the room, let you look at all the names in all the boxes, and then, if you choose to, switch two names with each other. For example, you could switch the names in boxes 35 and 77. You are only allowed to make one switch.
After you help with this task, you will be sent out of the prison and will not be able to communicate with the prisoners.
Before this strange game begins, you get to meet with the prisoners to discuss a strategy. This strategy must have two parts:
- How do you decide which names to switch, if any at all?
- How does each prisoner decide which 50 boxes he will open?
What plan do you come up with to ensure that the prisoners will all go free?