Table of Contents
1. Problem
There's a hundred boxes numbered 1 to 100, with a hundred papers with numbers written 1 to 100 inside in a random order.
A hundred prisoners numbered 1 to 100 each get to open 50 boxes, independent of other prisoners.
If all prisoners find the paper with the number matching their own number, all prisoners survives. Otherwise, they are all executed.
What is the best strategy, that maximized the probalibity of survaval?
2. Answer
Each prisoner starts with opening the box with the number that matches his own number, and consecutively opens the boxes with the number written on the paper in the box that he previously opened.
This works because, it only fails if the permutation of papers contains a cycle with the length larger than 50. The probability of failure is: \[ \frac{1}{100!}\left((100 - 51)!\binom{100}{51} 50! + \cdots + \binom{100}{100}99!\right) = \frac{1}{51} + \cdots \frac{1}{100}. \]
And the probability of success is about 30%.