[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 2100 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?