Has anyone proven the loop strategy is optimal?

Yes. Curtin and Warshauer proved in 2006 that no strategy can give the prisoners a higher survival probability.2

Does the strategy depend on the prisoners knowing $n$?

The protocol does, but the survival rate doesn't depend on $n$ once $n$ is large , it converges to $1 - \ln 2 \approx 30.69\%$.

What if prisoners can open more or fewer boxes?

Let $k$ be the number of boxes each prisoner can open. The survival probability is $1 - \sum_{\ell = k+1}^{n} \tfrac{1}{\ell}$.

Does it matter if the warden adversarially chooses the permutation?

If the warden knows the strategy, the survival rate drops to 0. Under the standard problem setup the loop strategy gives 31%.

Where did this riddle come from?

Posed by Anna Gál and Peter Bro Miltersen in 2003. The optimality analysis was completed by Curtin and Warshauer in 2006.

Probability · Viral

The 100 Prisoners Riddle

Random guessing gives the prisoners less than $0.0000\ldots1\%$ chance of survival. One clever strategy gives them 31%. Here is the strategy, the loop trick that powers it, and the proof.

Quick answer

The optimal strategy is the loop strategy: each prisoner first opens the box labeled with their own number, then opens the box labeled with whatever number they find inside, and continues following the chain. Survival probability: about 31.18%. Compare to the random strategy, where every prisoner independently flips coins: the chance all 100 succeed is $(1/2)^{100} \approx 7.9 \times 10^{-31}$. The loop strategy turns near-certain death into a 1-in-3 chance.

Open this in math.im for the full interactive version →

Canonical URL: https://math.im/blog/100-prisoners-hat-riddle.html

Loading post...