4 ms·
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'
by aidenn0 16y ago
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.
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.
- shasta 16y agoWell, you can parameterize this strategy with an arbitrary permutation P of {1, .. 100} in the following way. If you open box containing N, instead of next opening box N, you open box P(N). If the warden's placement of numbers defines permutation Q (box N contains Q(N)), then this new scheme will have each prisoner find his number if P composed with Q has no cycles of length greater than 50. Now, if you randomly picked a permutation P, then by symmetry since you don't know anything about the placement of numbers, you'd do just as well as with the original strategy. On the other hand, what you've proposed is that the warden has told you that choosing P to be identity results in failure. So if you exclude identity and pick one of the other permutations for your strategy, you'll fare a little tiny bit better on average. You can do even better than this by picking from a more specialized class of permutations for P. I'll leave the problem of finding the best class for P as a follow up.