Opening Boxes in a Courtyard


I got this problem from Rustan Leino, who got it from Clark Barrett, who got it from Robert Nieuwenhuis. I also heard it from Sean McCarthy.

I solved it and wrote up my solution.


100 prisoners agree on a strategy before playing the following game where they either all win or all lose. Find a strategy that lets them win with probability at least 1%; don't bother trying to prove that your strategy is optimal.

A courtyard has a line of 100 boxes numbered 1–100. Each box contains a different prisoner's name, and the distribution of the 100 prisoners' names among the boxes has been chosen uniformly randomly among such distributions. One at a time (in some unspecified order), each of the prisoners is taken to the courtyard. The prisoner gets to look in up to 50 of the boxes and see the names in them. If, after looking in 50 boxes, the prisoner has not found his own name, the game is over and all the prisoners lose. But, if the prisoner does find the box containing his name among the 50 boxes he looks into, then the prisoner is taken to the other side of the courtyard where he cannot communicate with the others. The boxes and courtyard are restored to their original state (in case the prisoner tried to manipulate them to communicate information), and the next prisoner is brought out into the courtyard. If all prisoners make it to the other side of the courtyard, they win.

Solution     Reveal