100 Prisoners and 100 Boxes

The problem
100 prisoners · 100 boxes · open ≤ 501234567891011121314151617181920each must find their own slipall survive ⇒ best probability?

100 prisoners are numbered 11 through 100100. A room contains 100 boxes, also numbered 11–100100. Each box contains a slip with one prisoner's number, placed in a uniformly random permutation.

One by one, prisoners enter and may open up to 50 boxes. To survive, each prisoner must find the slip with their own number. They can plan a strategy beforehand but cannot communicate once it starts.

Maximize the probability that all 100 prisoners survive.

Tempting (but wrong)
open at random · each P = 1/2 · all 100?(1/2)¹⁰⁰ ≈ 10⁻³⁰effectively zero"maybe a few percent with a smart strategy?"

"Random opening is hopeless." True: each prisoner finds their number with probability 1/21/2, so all 100 surviving has probability:

(12)100≈10−30\left(\tfrac{1}{2}\right)^{100} \approx 10^{-30}

— roughly the chance of winning the lottery three times in a row.

"Even with a smart strategy, maybe a few percent?" No. The actual answer is roughly 0.310.31. That's a factor of 102910^{29} better than random. The strategy is one of the most surprising results in elementary probability.