[evanchen]

The first prisoner opens 50 and sorts the 50 in alphabetical order (in an obvious manner). The second prisoner, upon seeing the sort, can quickly see if his name was in the original 50 (My name is Evan, I should be before Henry and after Bobby, etc). If he finds it quickly, he has plenty of "openings" to help sort the remaining boxes (maybe in a second row behind the first).

The rest of the prisoners should be able to easily find their names within 50 trials.

Success rate is PRETTY close to 50%.

[photon_off]

The boxes' states are restored after each prisoner leaves the room, so there's no way to sort them. The ideal solution would actually work even if the order of the boxes was shuffled each time.

[RiderOfGiraffes]

So how does this gel with "They cannot move the paper around between boxes"?