Jon Pretty

There are 100 prisoners, numbered 1-100. The prisoners' numbers are written onto 100 cards, put randomly into 100 envelopes numbered 1-100. They can't communicate, but are invited, one by one, to open 50 envelopes. If any prisoner fails to find his number, they all get killed.

This took longer than I'd like. Open the drawer w/your own matching number. If the number doesn't match, open the drawer for that number. Repeat. Now we're hoping that none of the prisoners are in a cycle of length > 50, but at least there can be only one such cycle.

I don’t understand. How does this increase the odds for any one prisoner to better than 50/50? I assume the answer requires later prisoners to know something based on success so far - how does this help with that?

The numbers in the drawers/envelopes are a permutation. If everyone starts with the envelope containing their number and keeps opening the envelope of the card in the previous one, they will all eventually get back to the same number via some sequence.

The sequence (or cycle) each prisoner lands may have length from 1 to 100, and there may be anything from 1 to 100 such sequences. But every prisoner is using the same set of cycles. This strategy means that the fates of the prisoners are no longer independent.

The probability that there's a cycle (there could only ever be at most one) longer than fifty turns out to be about 70%, and that corresponds to a prisoner needing to open more than fifty envelopes to get back to their number.