A Secretary in Need of a New Job..or a Rest
A "beyond-busy" careless secretary typed n letters (n>2) and addressed n envelopes...then repeatedly inserted one letter into one envelope at random. Find the probabilities of each of the following:
- Exactly n-1 letters went into the correct envelopes.
- No letter went in the correct envelope.
- Exactly 1 letter went in the correct envelope.
Hint: Work with simpler cases...n = 3, 4, 5, 6, ...etc. Look for patterns in your strategies and your conclusions.
Solution Commentary: As this is a famous problem, several solution approaches are available on the web. None will be given here.
However, note that for the second case of "No letter went in the correct envelope," the probability converges to 1/e quickly. How quickly? Well, the probability for n=6 is a good overall approximation value of 0.368, which leads to the unintuitive conclusion that the Prob(6 letters all go in wrong enevelopes) is basically the same as Prob(1000 letters all go in wrong envelopes). Do you believe that?