Derangement - Complete FAIL!

Source: Interview at one of the quant firms

Problem:
As posted in problems this and this, this is an extension to the derangement problem.
There are n men, n hats, one hat belonging to each person. A random permutation of hats is picked by the men. What is the probability that no person gets the correct hat?

Update (March 6, 2011)
Solution: Posted by Vipul Verma (Engineer at Portware, IIT KGP and University of South California Alumnus) in comments!

Comments

  1. The number of arrangements so that no one gets his own hat = n!*(1 - 1/1! + 1/2! - 1/3! + 1/4! ..... + (-1)^n/n!)

    Total number of arrangements = n!

    The prob that this happens = (1 - 1/1! + 1/2! - 1/3! + 1/4! ..... + (-1)^n/n!)


    Easy one....

    ReplyDelete
  2. Yes, easy one. Direct application of Inclusion Exclusion Principle. :)

    But your answer is wrong.

    Prob that no one gets his own hat = 1 - (Prob that at least one correct hat) = 1 - (nC1*1/n - nC2*1/(n*n-1) +..) = 1 - (1 - 1/2! + 1/3! .. ) = 1 - 1/e
    Prob: 1-1/e

    Your solution gives the probability that at least one person gets the correct hat.

    ReplyDelete
  3. Pratik, how is my answer wrong? How my soln is giving the prob. that at least one person gets the correct hat.

    If you look closely the expression you have got is same as what I got. The only difference is that expression has infinite terms which I don't understand why.

    Your series should not go to infinity. It should stop at n.

    ReplyDelete
  4. Pratik, if you see yours and vipul's answer are actually same.

    ReplyDelete
  5. I am sorry. My apologies.
    Yes your solution is correct. Our answers are same. Also, I should not have taken infinite terms. Thanks.

    ReplyDelete
  6. 1 - 1/2! + 1/3! .. = 1 - 1/e, and so the prob for no one get it right should be 1/e, right...?

    ReplyDelete
  7. @Yun.
    Yes you are correct.

    For large n

    Prob that no one gets his own hat = 1 - (Prob that at least one correct hat) = 1 - (nC1*1/n - nC2*1/(n*n-1) +..) = 1 - (1 - 1/2! + 1/3! .. ) = 1 - (1-1/e)
    Prob: 1/e

    ReplyDelete

Post a Comment