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.
-
Show this thread
-
At best, there's a 50% chance any one prisoner can find his number. It would seem like there's a probability of (½)¹⁰⁰ or 0.00000000000000000000000000008% that every prisoner could find his own number, if each were to check 50 envelopes at random.
2 replies 0 retweets 1 likeShow this thread -
They could certainly do even worse than this. If they all agreed in advance to open envelopes 1-50, then fifty of them would be guaranteed never to find their number and they'd all die. But could they come up with a strategy in advance which would improve their survival chances?
3 replies 0 retweets 0 likesShow this thread -
What makes this my favourite combinatorics problem is that there *is* a strategy which increases their likelihood of survival from 0.00000000000000000000000000008% to about 30%. So, what is the strategy, and why does it work?
12 replies 0 retweets 3 likesShow this thread -
Replying to @propensive
Must they necessarily open exactly 50 envelopes? Perhaps a prisoner finds their number, then continues to open envelopes until they reach 50 or until they find their number + 1. This would indicate to the person next to them where their number was.
1 reply 0 retweets 0 likes
I should have been clearer that the envelopes are all returned to the exact same initial state for each prisoner. All closed, each in the same physical state and position, each containing the same prisoner number. They can keep opening more, but they can't use that information.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.