12
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ "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. $\endgroup$ Jul 12, 2010 at 4:12
  • 8
    $\begingroup$ 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. $\endgroup$ Jul 12, 2010 at 4:58
  • $\begingroup$ Thanks, Qiaochu! You are encyclopedic. The reference to Math Intelligencer in the answer is exactly the one I've seen some years ago. $\endgroup$ Jul 12, 2010 at 6:05
  • $\begingroup$ Another reference is the book "The Raven's Hat" by Jonas Peters and Nicolai Meinshausen $\endgroup$ Jun 27, 2022 at 12:21
  • $\begingroup$ This post might get some new attention now that the Veritasium YouTube channel has a video about it: youtube.com/watch?v=iSNsgj1OCLA $\endgroup$
    – KConrad
    Jul 1, 2022 at 18:57

2 Answers 2

18
$\begingroup$

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. Zbl 1106.91004

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

$\endgroup$
1
10
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 25, 2011 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.