prashant wrote:
AkamaiBrah wrote:
sanjaymishra wrote:
There are 6 letters and 6 self addressed envelopes.What is the probability that none is correctly placed.
Consider this:
I believe the answer is 265/720 = 53/144.
Akamai,
Please elaborate on your answer
Solution:
First of all, IMO, although this problem looks basic, in reality this problem is WAY WAY WAY too difficult for the GMAT and will stump even graduate math students (it took me about 30 minutes).
We are looking for the solution of G(6) where G(n) = number of ways n items can be permuted such that they none of them match their original position. This is the same as having a deck of n cards numbered from 1 to n, then counting the ways you can shuffle the deck without any cards matching its position.
Consider this: it is obvious that when n = 1, G(n) must be ZERO, and when n = 2, G(n) = 1 (i.e., {2,1}), and when n = 3, G(n) = 2 (i.e., {2,3,1},{3,1,2}). By drawing out a probability tree, you will discover that G(4) = 9, and with a LOT of work and patience, G(5) = 44.
If you carefully watch how the tree is growing, you may notice that the results of G(n) refer back to the results of G(n-1) and G(n-2). With a little bit of work, we can see that a general recursive formula for G(n) is:
G(n) = (n-1)*(G(n-1)+G(n-2)) where n > 1 and G(1) = 0 and G(2) = 1.
If you build a table, then G(6) comes out to 5*(44 + 9) = 265. Since there are 6! or 720 ways to stuff the envelopes, the probabiltiy of getting them all wrong is 265/720 = 53/144.
(if you don't believe me, run a simulation).