[I got this problem from Clark Barrett, who got it from Robert Nieuwenhuis. Just when you thought you had heard all variations of prisoners and boxes…]

100 prisoners agree on a strategy before playing the following game:
One at a time (in some unspecified order), each of the prisoners is taken to a
courtyard where there is a line of 100 boxes. The prisoner gets to make
choices to open 50 of the boxes. When a box is opened, it reveals the name
of a prisoner (the prisoners have distinct names). The names written in
the boxes are in 1-to-1 correspondence with the prisoners; that is, each name is
found in exactly one box. If after opening 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 that contains his name among the
50 boxes he opens, then the prisoner is taken to the other side of the courtyard
where he cannot communicate with the others, the boxes are once again closed,
and the next prisoner is brought out into the courtyard. If all prisoners
make it to the other side of the courtyard, they win.

One possible strategy is for each prisoner to randomly select 50 boxes and
open them. This gives the prisoners 1 chance out of 2^{100}
to win–a slim chance, indeed. But the prisoners can do better, using a
strategy that for a random configuration of the boxes will give them a larger
chance of winning. How good a strategy can you develop?

©2019 K.R.M. Leino - Split Template by One Page Love