4
$\begingroup$

A secretary types three letters and the three corresponding envelopes. In a hurry, he places at random one letter in each envelope. What is the probability that at least one letter is in the correct envelope?

My effort:

There are three choices of an envelope for the first letter, then there are two choices of an envelope for the second letter, and finally there is one choice of an envelope for the third letter, thereby making a total of six possible choices.

Now we should first try to compute the probability that none of the three letters is in the correct envelope. But how to compute this probability?

Once we know this probability, then our required probability is one minus this probability.

$\endgroup$
1
  • $\begingroup$ The magic word you want to look up is derangements. (Inclusion-exclusion gets you most of the way here) $\endgroup$ Aug 6, 2014 at 7:36

6 Answers 6

4
$\begingroup$

For $3$ objects this is fairly trivial, as you can simply inspect each combination:

  • $123:$ all letters are in the correct envelope
  • $132:$ letter #$1$ is in the correct envelope
  • $213:$ letter #$3$ is in the correct envelope
  • $231:$ no letter is in the correct envelope
  • $312:$ no letter is in the correct envelope
  • $321:$ letter #$2$ is in the correct envelope

In $4$ out of $6$ combinations, there is at least one letter in the correct envelope.

Hence the probability of having at least one letter in the correct envelope is $\dfrac{4}{6}$.

$\endgroup$
3
$\begingroup$

Because the Derangement formula given above is also the components of a series to calculate the constant e the "all fails" for any number (n) envelopes can be given by

n!/e rounded to the nearest integer

The constant e has the value (to 9dp) of 2.718281828

So for the first few

envelopes, all-possibilities, all-fails (remember rounded to nearest integer)

2         2! =    2          2!/e =    1

3         3! =    6          3!/e =    2

4         4! =   24          4!/e =    9

5         5! =  120          5!/e =   44

6         6! =  720          6!/e =  265

7         7! = 5040          7!/e = 1854

etc.
Note that the overall probability tends to 1/e or about 37% - and gets closer to 1/e as the number of envelopes increases.

The value given by [n!/e] (where the square brackets denote "nearest integer to") is known as the subfactorial of n and can be written !n

$\endgroup$
2
$\begingroup$

A derangement is a permutation of the elements of a set such that none of the elements appear in their original position.given by: $$D(n)=n!\left(\frac1{0!}-\frac1{1!}+\frac1{2!}\cdots\frac1{n!}\right)=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$$

So you ways of none in correct envelope is: $$D(3)=3!\left(\frac1{0!}-\frac1{1!}+\frac1{2!}-\frac1{3!}\right)=2$$

It is basically derived from inclusion-exclusion principle, and if you don't know the formula you can use inclusion-exclusion principle.

Also there are very few encelopes, i.e.3, so you can count manually too(the total arrangements).

$\endgroup$
1
$\begingroup$

The six assignments of the letters to the envelopes are 123, 132, 213, 231, 312, 321. How many of them have at least a letter in the right envelope ?

Divide this number by 6.

HINT

The assignments with at least one letter in the right envelope are of the form 1??, ?2? and ??3. Replacing the ? in every possible way gives 123, 132, 123, 321, 123, 213. And after removing duplicates, 123, 132, 321, 213.

Alternatively, consider all disallowed assignments (no letter in the right envelope): they must be of the form 2?? or 3??. Among 2??, only 231 is disallowed, and among 3??, only 312.

$\endgroup$
2
  • $\begingroup$ Yves Daoust, you're right, there are four cases in which at least one of the letters is in the correct envelope, so the desired probability is $4/6 = 2/3$. Am I right? But don't you think this approach would become too impractical if we had, say, 100 letters to be put into 100 envelopse? What would be a better approach in that case? $\endgroup$ Aug 6, 2014 at 7:51
  • 1
    $\begingroup$ This is answered by @Aditya. Anyway, I advise you to try the cases for 4 and possibly 5 letters by hand to get a better feeling about permutations. $\endgroup$
    – user65203
    Aug 6, 2014 at 7:54
1
$\begingroup$

Let the envelopes be A, B, and C; designated for letters {A, B, C} in that order respectively. Now taking the complementary case where all letters are enclosed in the wrong envelopes, we have the permutations {B, C, A} and {C, A, B}, in that order. Overall, we have 3! = 6 ways of arranging the letters.

Hence the probability of enclosing the envelopes in the wrong order would be 2/6 = 1/3, whilst the required probability that at least one is in the right envelope would be 1 - 1/3 = 2/3.

$\endgroup$
0
$\begingroup$

Let us have n letters corresponding to which there exist n envelopes bearing different addresses.

A Match occurs if $Letter_{i}$ gets into $Envelope_{i}$ , $Letter_{j}$ gets into $Envelope_{j}$. Let us denote this event as $E_{i}$ .

A NO Match occurs if $Letter_{i}$ gets into $Envelope_{j}$ , $Letter_{j}$ gets into $Envelope_{i}$. Let us denote this event as $\overline{E_{i}}$ .

$E_{i}$ : Denote the Event where that the ith object occupies the ith position corresponding to its number. Then, the probability 'p' that P(None of the objects occupies the place corresponding to its number) = P( No Letter will be in its proper Envelope corresponding to its number) is given by : $ p = P(\overline{E1} \cap \overline{E2} \cap \overline{E3}.... \cap \overline{En} ) = 1 - P(\text{Atleast one of the objects occupies the place corresponding to its number})= 1 - P(\text{Atleast One Letter will be in its proper Envelope corresponding to its number})= 1 - P(E1 \cup E2\cup E3.... \cup En) = 1 - [\sum_{i=1 }^{n}P(E_{i}) - \sum_{i=1 }^{n}\sum_{j=1 }^{n}P(E_{i} \cap E_{j})....+(-1)^{n-1}P(E_{1} \cap E_{2}\cap E_{3}....... \cap E_{n}) ]= 1 - [\frac{\binom{n}{1}}{n} - \frac{\binom{n}{2}}{n(n-1)} + \frac{\binom{n}{3}}{n(n-1)(n-2)} - ..... + \frac{(-1)^{n-1}}{n(n-1)(n-2)...3.2.1} ] = 1- [ 1- \frac{1}{2!} + \frac{1}{3!}-...+\frac{{(-1)^{(n-1)}}}{n!}]= \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - ........ + \frac{(-1)^{(n)}}{n!} = \sum_{k = 0 }^{n}\frac{(-1)^{k}}{k!}$ ......................................................................

But for large n :

p = $1-1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} - ........... = e^{-1}$

And, the Probability of Atleast One match : $1 - p = (1-e^{-1})$

.........................................................................

Therefore, P(None of the n letters goes to the correct envelope ) = $\sum_{k = 0 }^{n}\frac{(-1)^{k}}{k!}$

Therefore, $P(\text{Atleast One Letter will be in its proper Envelope corresponding to its number})= [ 1- \frac{1}{2!} + \frac{1}{3!}-...+\frac{{(-1)^{n-1}}}{n!}]$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .