100 Prisoners, 100 Boxes: Proof of Optimality - MathOverflow

100 Prisoners, 100 Boxes: Proof of Optimality

2010-07-12T04:05:19Z

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?

Answer by shreevatsa for 100 Prisoners, 100 Boxes: Proof of Optimality

2010-07-12T04:26:26Z

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

Answer by Pietro Majer for 100 Prisoners, 100 Boxes: Proof of Optimality

2010-07-12T07:11:11Z

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.