- 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? |

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:

- Assuming the envelopes are in fixed positions, the total number of ways of ordering the n letters to go into the n envelopes is
n!(n factorial).- If r of the n letters are matched correctly, the number of ways of choosing which r of the n are matched correctly is
^{n}C_{r}- We will use the notation
N(0/m)to stand for "the number of ways of getting no correct matches with m letters and m envelopes.- There is only one way that all letters can be correctly matched.
- There is no way that all but one letter can be correctly matched (think about it...!)

**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 matches | 2 | 1 | 0 |

Number of ways | 1 | 0 | 1 |

**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 = ^{3}C_{1} × 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 matches | 3 | 2 | 1 | 0 |

Number of ways | 1 | 0 | 3 | 2 |

**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 = ^{4}C_{2} × 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 = ^{4}C_{1} × 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 matches | 4 | 3 | 2 | 1 | 0 |

Number of ways | 1 | 0 | 6 | 8 | 9 |

**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 = ^{5}C_{3} × 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 = ^{5}C_{2} × 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 = ^{5}C_{1} × 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 matches | 5 | 4 | 3 | 2 | 1 | 0 |

Number of ways | 1 | 0 | 10 | 20 | 45 | 44 |

**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