Here's a new brain teaser. The warden is a mathematician, and instead of arranging them randomly, he ensures that there is a cycle of at least 51. However he's not too cruel, so he tells the prisoners that he has done this.<p>I'm pretty sure that since this is less random than the original version the survival rate would go up, but I haven't figured out how to do this.
If the boxes are in a random jumble when the prisoner enters, there may be no practical way of having 100 prisoners consistently assign an ordering from 1 to 100 for the boxes. The approach outlined will then fail.<p>Were I a particularly evil warden, I could meticulously place all the boxes in the same such "jumble" after each prisoner left. One of the prisoners would certainly derive a different ordering of the boxes than one of the other prisoners. The approach might still have a better than random chance of succeeding, but it would be lower than that outlined in the article, since there are now two (or more) chances for a cycle of length greater than 50.
For the people who would go for an analytical solution rather then monte-carlo: for a large number of prisoners the probability that they all find their numbers tends to 1 - ln(2) ~= 0.3069
I'm not seeing any obvious trick here. Trying it with just two prisoners, two boxes and one look, I can't see a way to do better than chance. I'm just wondering if it's something like the two envelopes problem, where you can on average do better by switching based on a monotonic function of the amount in the first envelope. Perhaps there is a way of picking the boxes based on your number that does better than average, even if its just a little bit. Any hints?