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?
Best Answer
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:
If you can't access the paper, you can see it explained (along with the original puzzle and strategy) in detailed here (or a sketch here).