The warden knows the chain strategy
A hundred prisoners plan the classic strategy: each opens the box bearing their own number, then the box bearing the number found inside, and so on, up to fifty boxes. Against a random arrangement this frees everyone about 31 per cent of the time.
The warden overhears the plan. He is allowed to arrange the slips in the boxes however he likes, and he wants the prisoners to fail.
- Show that the warden can guarantee they fail.
- The prisoners learn that the warden knows. Before entering, and still without any communication once the first prisoner goes in, can they modify the plan so that the warden cannot push their success chance below about 31 per cent, no matter how he arranges the boxes?
Show a hint
The strategy fails exactly when the arrangement contains a cycle longer than 50. The warden can build such a cycle on purpose. To stop him, the prisoners need the effective arrangement to be random from his point of view, even though the physical arrangement is his choice.
Your answer
Solving needs a free account
Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.
Discussion
💡 Discussion rules
- No full solutions here. Hints and approaches only.
- Complexity, edge cases and intuition are the point.
- Interview experiences are welcome. Respect your NDAs.
Loading discussion…
Learn the concepts
The theory behind this question.