There's a chestnut about 100 prisoners, labeled 1 through 100, and 100 boxes, each with a number 1 through 100 in it. Each prisoner, completely independently of the others, tries to find the box which has their label in it. If they all find their label, they win.


They each get to sequentially look inside 50 boxes, meaning they look in the first box, and based on the response, decide which box to look into next, etc. They can't alter the boxes or communicate with other prisoners in any way. Of course, they agree on a strategy beforehand.


There is a really lovely strategy based on cycle representations of permutations (I have a soft spot for puzzles which hinge on cycle representations of permutations), but is there a lovely proof that its optimal? Or any proof?



100 Prisoners, 100 Boxes: Proof of Optimality
I'm not sure this is at an appropriate level for Math Overflow, but while the question is open... Yes, there is a proof that the strategy is optimal, and it's in [this paper](https://doi.org/10.1007/BF02986999):


* Eugene Curtin and Max Warshauer, *The locker puzzle*, The Mathematical Intelligencer, Volume 28, Number 1 (March 2006), pages 28–31. [Zbl 1106.91004](https://zbmath.org/?q=an:1106.91004)


If you can't access the paper, you can see it explained (along with the original puzzle and strategy) in detailed [here](https://web.archive.org/web/20150209042059/https://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/) (or a sketch [here](https://shreevatsa.wordpress.com/2009/08/10/eugene-curtain-and-max-washauer/)).


