Paychecks and Envelopes

Date: 10/07/97 at 12:01:10
From: Babette Martin
Subject: Probability

Five paychecks and envelopes are addressed to five different people.  
If the paychecks are randomly inserted into the envelopes, what is the 
probability that (a) exactly one will be inserted in the correct 
envelope, and (b) at least one will be inserted in the correct 
envelope?

We were able to figure the problem out when we only had four checks 
and envelopes because we could list all the possible combinations.  
It is almost impossible for us to list the 120 different combinations 
for the 5 paychecks.  Help - we need a better way to figure this 
problem out!  We are anxiously waiting for your suggestion.  

Thanks!

Date: 10/07/97 at 16:25:56
From: Doctor Anthony
Subject: Re: Probability

If we let A be the event that paycheck A is in correct envelope and 
similarly B is event that paycheck B is in correct envelope, then

P(A) = 1/5  

P(A and B) = 1/5 x 1/4

Now use the inclusion, exclusion formula to get probability that A or 
B or C .... or E are correctly placed.

P(A or B or C .... or E) = P(A) + P(B) + P(C) + P(D) + P(E)
                         - P(A and B) - P(B and C) -....
                         + P(A and B and C) + P(B and C and D) + ....
                         - P(A and B and C and D) - P(...) -......
                         + P(A and B and C and D and E)

                         = 5 x (1/5)
                           - 5C2 x (1/5)(1/4)
                           + 5C3 x (1/5)(1/4)(1/3)
                           - 5C4 x (1/5)(1/4)(1/3)(1/2)
                           +  (1/5)(1/4)(1/3)(1/2)(1/1)

         5x4    1    5x4x3     1     5x4x3x2      1          1
   = 1 - --- x --- + ----- x ----- - ------- x ------- + --------
         1x2   5x4   1x2x3   5x4x3   1x2x3x4   5x4x3x2   5x4x3x2x1

   = 1 - 1/2! + 1/3! - 1/4! + 1/5!


This is a probability that at least one paycheck is correctly placed.

The chance that none is correctly placed is 1 - (above result)

   = 1 - 1 + 1/2! - 1/3! + 1/4! - 1/5!

   = 1/2! - 1/3! + 1/4! - 1/5!

To find the probability that exactly one is correctly placed, we need 
to find the total number of ways with 1 correct and 4 incorrect.

We can use the result of last section to see the number of ways where 
4 checks are all incorrect.

If we had 4 checks and 4 envelopes, the probability that all are 
incorrect would be  1/2! - 1/3! + 1/4!

Therefore the number of arrangements with all incorrect is given by

    4!(1/2! - 1/3! + 1/4!) = 12 - 4 + 1 = 9

Now imagine the checks laid out in a row, and the envelopes in a 
matching row.

If the first check is the only correct one opposite its envelope, then 
there are 9 arrangements for the other 4 all putting them in the 
incorrect envelope. Similarly, if the second one is the only correct 
one, then this can be associated with 9 arrangements for the other 4, 
which will all be incorrect. Similarly for the third, fourth, and 
fifth checks, they can each be associated with 9 arrangements, making 
the other 4 all incorrect.

So the total number of arrangements in which just one is correctly 
placed is:

        5 x 9 = 45

The total number of possible arrangements is of course 5! = 120, so 
the probability that exactly one is correct is

                    45/120 =  3/8

We have already seen that the probability of at least one being 
correct is:

  1 - 1/2! + 1/3! - 1/4! + 1/5! =  19/30

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/