Probability


  • From: T J Noonie
  • Date: 12 March 1999
  • Subject: The "drunken secretary" problem

Can you show me how to go about solving the following problem:

If five letters are put into five addressed envelopes at random, what is the probability that none of the envelopes contains the correct letter?


Maths Help suggests:

This is a well known problem in probability. It is known as the "drunken secretary problem" - conjuring up images of a secretary who has had a few too many drinks not bothering about how the letters are put into the envelopes.

It is quite a tricky problem. There are several methods of approaching it, each needing maths of at least A-level standard. The one below is not necessarily the shortest, but we think it is the easiest to follow and try yourself.

We will start with the case of 2 letters and 2 envelopes, and then build it up to 3, 4, and 5 letters and envelopes. We could of course go further. In each case, we will work out the number of ways of getting 0 correct matches, 1 correct match, 2 correct matches etc, and we will need to do this in reverse order. When we have a table of the number of ways of getting all the different numbers of matches, we can easily find the probabilities.

Some essential background results before we start:

CONSIDER THE CASE OF 2 LETTERS AND 2 ENVELOPES

There are 2! = 2 ways in total.

Number of ways of 2 correct matches = 1 (always)

Number of ways of getting 1 correct match = 0 (always)

Number of ways of getting 0 correct matches is 2 - (1 + 0) = 1
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:
Correct matches210
Number of ways 101

CONSIDER THE CASE OF 3 LETTERS AND 3 ENVELOPES

There are 3! = 6 ways in total.

Number of ways of 3 correct matches = 1 (always)

Number of ways of getting 2 correct matches = 0 (always)

Number of ways of getting 1 correct match = 3C1 × N(0/2) = 3×1 = 3
Note this is "number of ways of choosing the one which matches" times "number of ways that none of the remaining ones match". N(0/2) is taken from the previous table.

Number of ways of getting 0 correct matches is 6 - (1 + 0 + 3) = 2
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:
Correct matches3210
Number of ways 1032

CONSIDER THE CASE OF 4 LETTERS AND 4 ENVELOPES

There are 4! = 24 ways in total.

Number of ways of 4 correct matches = 1 (always)

Number of ways of getting 3 correct matches = 0 (always)

Number of ways of getting 2 correct matches = 4C2 × N(0/2) = 6×1 = 6
Note this is "number of ways of choosing the two which match" times "number of ways that none of the remaining ones match". N(0/2) is taken from the previous table.

Number of ways of getting 1 correct match = 4C1 × N(0/3) = 4×2 = 8
Note this is "number of ways of choosing the one which matches" times "number of ways that none of the remaining ones match". N(0/3) is taken from the previous table.

Number of ways of getting 0 correct matches is 24 - (1 + 0 + 6 + 8) = 9
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:
Correct matches43210
Number of ways 10689

CONSIDER THE CASE OF 5 LETTERS AND 5 ENVELOPES

There are 5! = 120 ways in total.

Number of ways of 5 correct matches = 1 (always)

Number of ways of getting 4 correct matches = 0 (always)

Number of ways of getting 3 correct matches = 5C3 × N(0/2) = 10×1 = 10
Note this is "number of ways of choosing the three which match" times "number of ways that none of the remaining ones match". N(0/2) is taken from the previous table.

Number of ways of getting 2 correct matches = 5C2 × N(0/3) = 10×2 = 20
Note this is "number of ways of choosing the two which match" times "number of ways that none of the remaining ones match". N(0/3) is taken from the previous table.

Number of ways of getting 1 correct match = 5C1 × N(0/4) = 5×9 = 45
Note this is "number of ways of choosing the one which matches" times "number of ways that none of the remaining ones match". N(0/4) is taken from the previous table.

Number of ways of getting 0 correct matches is 120 - (1 + 0 + 10 + 20 + 45) = 44
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:
Correct matches543210
Number of ways 1010204544

This procedure can be continued recursively for higher numbers of letters and envelopes.

So the answer to your question is:
The probability of no correct matches for 5 letters and 5 envelopes is 44/120 = 11/30


Return to contents list