[StatGuy]

Hi!

In my statistics class we have been given the classic problem asking, "Five letters are written to five different people and five envelopes are appropriately addressed. If each letter is placed into a randomly selected envelope (one letter per envelope), compute the probability P1 that at least one person receives the correct letter". A second part of the question asks, "How would your answer change if 100 letters were written?"

I have found some information on the web regarding the inclusion/exclusion principle that applies to this problem but I am having a hard time really understanding the logic completely. If Ms Griffiths or someone else could help explain this a little bit in Head First style I would really appreciate it.

Thanks,
StatGuy

[rusdemezale]

probability at least 1 of the 5 letters gets into the correct envelope =
1 - P(none of the letters lands in the correct envelope)

P(none of the letters lands in the correct envelope) = (4/5)*(3/4)*(2/3)*(1/2)*(1/1) = 1/5

1-(1/5) = (4/5) is the answer then ...

for 100 => it will be 99/100
It is intuitive, like in lottery. If millions of people play, you have less chance to win

[dawng]

Hi guys,

The probability that at least one person gets the correct letter is actually a little bit lower than you might expect.

Let's start by looking at a similar problem with just three envelopes, marked A, B and C. We want to find the probability that at least one of these has the correct letter inside it. In other words, we need to find P(A or B or C) where P(A) is the probability that envelope A contains letter A, and so on.

Now, we can find P(A or B or C) using the formula

P(A or B or C) = P(A) + P( + P© - P(A and - P(A and C) - P(B and C) + P(A and B and C)

so if we know what all the individual probabilities are, we'll have the answer.

Let's start with P(A). As there are three envelopes, the probability that envelope A will contain the correct letter is (1/3) as there's a 1 in 3 chance of letter A being in that envelope. It's a similar result for envelopes B and C, so
P(A) = P( = P© = (1/3)

If we take P(A and next, the probability is (1/3)*(1/2). We multiply (1/3) by (1/2) because once one letter has been placed correctly in an envelope, there are only two letters left. If we do the same thing for P(A and C) and P(B and C), we get
P(A and = P(A and C) = P(B and C) = (1/3)*(1/2) = (1/6)

Similarly,
P(A and B and C) = (1/3)*(1/2)*(1) = (1/6)

If we put all of these into the formula above, we get

P(A or B or C) = 3*(1/3) - 3*(1/6) + (1/6)
= 1 - (1/2) + (1/6)
= 1 - (1/2!) + (1/3!)

So that's the result for three letters, but what if there are more? If we go through the same steps for four letters, we get

P(A or B or C or D) = 1 - (1/2!) + (1/3!) - (1/4!)

Can you see a pattern forming? You alternately add and subtract numbers, and the denominator of each of the numbers is given by a factorial. If we extend this to five letters, we get

P(A or B or C or D or E) = 1 - (1/2!) + (1/3!) - (1/4!) + (1/5!)
= 19/30

The pattern continues for increasing numbers of envelopes and letters, which should help you with the second part of your problem

Hope this helps,
Dawn

[rusdemezale]

P(at least 1 envelope is correct) = P(none is correct)'
(for 3 envelopes)
= 1 - (2/3)*(1/2) = 2/3
what am I missing here?

[dawng]

That method gives the right answer when there are just 2 or 3 envelopes, but it falls down when there are 4 or more. To see this in action, let's try it with 4 envelopes. Your approach gives

P(at least one letter is in the right envelope) = 1 - (3/4)(2/3)(1/2) = 3/4

Now, if you grab a pen and paper and write down all the ways in which you can allocate letters to envelopes so that there's at least one correct match, you find there are 15 possible arrangements. There are 4! ways of arranging the letters in total, so this gives

P(at least one letter is in the right envelope) = 15/4! = 15/24 = 5/8

This is different to the answer above.

The reason for the difference is that it's trickier to calculate the probability that none of the letters ends up in the right envelope than you might expect.

Let's start with the first envelope, envelope A. There are 4 letters that can go into envelope A and 3 of them will be incorrect, so P(A is incorrect) = 3/4.

Now let's move onto envelope B. There are 3 remaining letters that can go into envelope B, and it's tempting to say that 2 of them will be incorrect. The trouble is, the real answer all depends on what went into envelope A. As an example, if we put letter B into envelope A leaving behind letters A, C and D, then the probability that envelope B will be filled incorrectly is 3/3; it's only 2/3 if envelope A was incorrectly filled with letter C or D. This means that overall, the probability of incorrectly filling envelopes A and B is not (4/3)(2/3), which is why you get a different final answer.

Dawn

[crimona]

That method gives the right answer when there are just 2 or 3 envelopes, but it falls down when there are 4 or more. To see this in action, let's try it with 4 envelopes. Your approach gives

P(at least one letter is in the right envelope) = 1 - (3/4)(2/3)(1/2) = 3/4

Now, if you grab a pen and paper and write down all the ways in which you can allocate letters to envelopes so that there's at least one correct match, you find there are 15 possible arrangements. There are 4! ways of arranging the letters in total, so this gives

P(at least one letter is in the right envelope) = 15/4! = 15/24 = 5/8

This is different to the answer above.

The reason for the difference is that it's trickier to calculate the probability that none of the letters ends up in the right envelope than you might expect.

Let's start with the first envelope, envelope A. There are 4 letters that can go into envelope A and 3 of them will be incorrect, so P(A is incorrect) = 3/4.

Now let's move onto envelope B. There are 3 remaining letters that can go into envelope B, and it's tempting to say that 2 of them will be incorrect. The trouble is, the real answer all depends on what went into envelope A. As an example, if we put letter B into envelope A leaving behind letters A, C and D, then the probability that envelope B will be filled incorrectly is 3/3; it's only 2/3 if envelope A was incorrectly filled with letter C or D. This means that overall, the probability of incorrectly filling envelopes A and B is not (4/3)(2/3), which is why you get a different final answer.

Dawn

I have a similar but difficult problem that's got me baffled for a while now. Please help me if you can. Thanx

There are 6 sealed envelopes, whose sizes are listed here:
4.125" x 9.5" Business envelope
3.5" x 9.25" Chou 30 envelope (from Japan)
4" x 5.5" Greeting card envelope
9" x 12" Large manila envelope
7.5" x 10.5" Small manila envelope
9.125" x 9.125" Square envelope

Each envelope has a single digit written on the outside of it. Some of the envelopes are inside of others; there's even one envelope that's inside an envelope that's inside another one. All of the envelopes are lying flat; They haven't been folded, cut, rolled, wrinkled, or otherwise modified them to make them fit.

You'll need to figure out what number is written on each envelope, from the clues below:
Exactly four of the envelopes are inside of other envelopes. One of the two "outside" envelopes has a transparent window, through which the number 7 is visible. Except for that window, the envelopes are opaque.

The number on the greeting card envelope equals the number on one of the other envelopes; there are no other duplicate numbers.

The product of the 6 numbers is 20160.

The number on the square envelope equals the number of envelopes inside it.

The number on the Chou 30 envelope is the sum of two of the other numbers.

The number on the large manila envelope equals the average of the numbers on the envelopes inside it.

[Asit Pal]

dawng is absolutely correct! I just want to give a bit more detail..

Solution 1:

Let's start with a small problem. Assume that there are 4 letters and 4 addressed envelops. Let A be the event that letter A is in its correct envelop and similarly let B be the event that letter B is in its correct envelop. Then

P(A) = 1/4, P(B) = 1/4 and
P(A and B) = 1/4*1/3
...............

Now use the inclusion-exclusion principle to get the probability that A or B or C or D is correctly placed.

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

= 4C1*1/4 - 4C2*1/4*1/3 + 4C3*1/4*1/3*1/2 - 4C4*1/4*1/3*1/2*1/1
= 1 - ((4*3)/2)*1/4*1/3 + ((4*3*2)/(3*2))*1/4*1/3*1/2 - 1*1/4*1/3*1/2*1/1
= 1 - 1/2! + 1/3! - 1/4!

Note that it's following a pattern! For 5 letters and 5 envelops the result will be
1 - 1/2! + 1/3! - 1/4! + 1/5!

We can generalize it for n letters and n envelops, and the result is
1 - 1/2! + 1/3! - 1/4! + 1/5! - .... - ((-1)^n)/n! which is the probability that at least one letter goes to the correct address.

For Twists:

So the chance (probability) that none of the letters is correctly placed is
1 - (1 -1/2! + 1/3! - .... - ((-1)^n)/n!)
= 1/2! - 1/3! + .... + ((-1)^n)/n!

So the number of ways of sending all letters to the wrong addresses is
n!*(1/2! - 1/3! + 1/4!- .... + ((-1)^n)/n!)

Posting Solution 2 in the next post...that's even more interesting!!

Asit Pal
asitbpal@gmail.com

This post has been edited by Asit Pal: 03 September 2009 - 06:30 PM

[SteveT]

I have a similar but difficult problem that's got me baffled for a while now. Please help me if you can. Thanx

There are 6 sealed envelopes, whose sizes are listed here:
4.125" x 9.5" Business envelope
3.5" x 9.25" Chou 30 envelope (from Japan)
4" x 5.5" Greeting card envelope
9" x 12" Large manila envelope
7.5" x 10.5" Small manila envelope
9.125" x 9.125" Square envelope

Each envelope has a single digit written on the outside of it. Some of the envelopes are inside of others; there's even one envelope that's inside an envelope that's inside another one. All of the envelopes are lying flat; They haven't been folded, cut, rolled, wrinkled, or otherwise modified them to make them fit.

You'll need to figure out what number is written on each envelope, from the clues below:
Exactly four of the envelopes are inside of other envelopes. One of the two "outside" envelopes has a transparent window, through which the number 7 is visible. Except for that window, the envelopes are opaque.

The number on the greeting card envelope equals the number on one of the other envelopes; there are no other duplicate numbers.

The product of the 6 numbers is 20160.

The number on the square envelope equals the number of envelopes inside it.

The number on the Chou 30 envelope is the sum of two of the other numbers.

The number on the large manila envelope equals the average of the numbers on the envelopes inside it.

[SteveT]

Hi,
Just came across this.
Interesting puzzle. From looking at this, I can immediately conclude one of the other numbers is a 5, and at least one of the remaining numbers must be an even number. Otherwise, you could not have a product that is a power of ten.
I will ponder over this a bit more...
Steve

[ankitpdr]

There are some attention-grabbing closing dates on this article but I don’t know if I see all of them heart to heart. There’s some validity but I will take hold opinion until I look into it further. SEO Services | SEO India Good article , thanks and we want more!