The hundred boxes numbered

1. Opening 50 boxes at random gives a collective probability of practically zero.
2. Treat the arrangement of numbers inside the boxes as a permutation.
3. Each prisoner must start with the box that has his own number written on it and follow the number he finds.

Answer: Each prisoner must follow the cycle that begins on the box with his own number. The strategy is this: 1. Prisoner $i$ first opens box number $i$.

1. If you find your own number inside, you are done.
2. If you find another number, open the box that has that number written outside.
3. Repeat the process until you find its number or until you have opened 50 boxes. Why does it work? The placement of the numbers inside the boxes defines a permutation of numbers from 1 to 100: each numbered box points to the number it contains. By starting with the $i$ box and following the numbers found, the prisoner goes through exactly the cycle of that permutation that contains his number. It will find its number if and only if that loop has length at most 50. Therefore, they all survive exactly when the permutation has no cycle length greater than 50. The probability that a cycle of length $k$ exists, for $k>50$, is $1/k$. Since there cannot be two cycles of length greater than 50 at the same time, the probability of failure is: $$

\frac1{51}+\frac1{52}+\cdots+\frac1{100}.

$$ So the probability of success is: $$

1-\left(\frac1{51}+\frac1{52}+\cdots+\frac1{100}
ight),
$$ approximately 31%. Compared to opening boxes at random, whose collective probability would be close to $(1/2)^{100}$, the cycle strategy is enormously better.