# 100 Prisoners, 100 Boxes: Proof of Optimality

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?

-
"There is a really lovely strategy...": can you give more details on that? I've heard of the problem some years ago and remember that there was a publication about it (stated however a little bit differently), but it's almost impossible to find it now. – Wadim Zudilin Jul 12 '10 at 4:12
The strategy is that the assignment of prisoner labels to box labels determines a permutation, and one iterates that permutation: prisoner i looks at box i, and if box i has prisoner j's label in it, prisoner i next looks at box j, and so forth. The prisoners all find their labels if and only if the permutation has no cycle of length greater than 50. – Qiaochu Yuan Jul 12 '10 at 4:58
Thanks, Qiaochu! You are encyclopedic. The reference to Math Intelligencer in the answer is exactly the one I've seen some years ago. – Wadim Zudilin Jul 12 '10 at 6:05

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:

• Eugene Curtin and Max Warshauer, The locker puzzle, The Mathematical Intelligencer, Volume 28, Number 1 (March 2006), pages 28–31.

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).

-
Indeed a PDF of the paper is available here: maths.tcd.ie/~onash/pity_the_prisoners_files/locker-problem.pdf – Oliver Nash Apr 17 '12 at 10:39

To prove that the strategy described above by Qiaochu Yuan gives the best chances of winning, the idea is as follows: consider a more fair, and more trivial variant of the game, where the rules are as before, but all open boxes remain open, so that each prisoner takes advantage of the information gathered; one may think that the boxes are simply being opened in some order by the same person. This sort of relaxation of the game is quite trivial to analyse: it consists essentially in choosing in which order to open the boxes, and of course whether or not the chosen permutation is winning, it's just random (and a priori no choice of a permutation is better than another). It turns out that the winning permutations for this game are as many as the permutations with no cycle longer than 50. Indeed, if $\lambda(1),\dots,\lambda(100)$ is the corresponding sequence of the labels found, let's divide it in consecutive substrings so that each string ends with the lower not yet found label. This subdivision may be seen as the cycle decomposition of a permutation $\sigma$, and of course it is a lucky choice if and only if $\sigma$ has no cycle of length greater that 50. So one can't do better than that even in the original game.

-
I mean, each prisoner has to stop opening the boxes as soon as he finds his label. Sorry if this point wasn't clear. (I assumed this was a rule of the previous game too: there, nobody else is watching and there is no point in opening all 50 boxes once the label is found!). In particular, in this variant, if the prisoner's label has already been found, he does nothing. – Pietro Majer Oct 25 '11 at 19:58