Results 1 to 2 of 2

Thread: Two packs of cards....

  1. #1
    Contributing Member
    Join Date
    Sep 2006
    Answers
    962

    Two packs of cards....

    Players Jhon and James each have a well shuffled standard pack of cards, with no jokers. The players deal their cards one at a time, from the top of the deck, checking for an exact match. Player Jhon wins if, once the packs are fully dealt, no matches are found. Player James wins if at least one match occurs. What is the probability that player Jhon wins?

    -------------------
    suresh


  2. #2
    Contributing Member
    Join Date
    Sep 2006
    Answers
    962

    Re: Two packs of cards....

    Hi Friends,

    Here is the answer for this puzzle...Let us assume A is Jhon and B is James.

    Since player A is dealing from a shuffled (randomized) pack, the probability that A wins is independent of the order in which B's cards are dealt. So, without loss of generality, we can assume B's cards are dealt in order: 1, 2, 3, ... , 52. Therefore the probability that player A wins is the fraction of permutations of (a1, a2, ... , a52) for which ai i, for all i from 1 to 52. Such permutations are known as derangements.

    Let d(n) be the number of derangements of n elements. Then, by the Inclusion-Exclusion Principle,

    d(n) = (total number of ways to deal n cards)
    - sum over i (number of deals for which ai = i)
    + sum over distinct i, j (number of deals for which ai = i and aj = j)
    - sum over distinct i, j, k (number of deals for which ai = i, aj = j and ak = k)
    ± number of ways in which ai = i, for all i from 1 to n
    (with the final sign dependent on the parity of n)

    Here, we start with n! deals, subtract those with one matching card, then add back the number with two matching cards (we just counted these combinations twice), and so on.

    So d(n) = n! - nC1 · (n-1)! + nC2 · (n-2)! + ... ± nCn · (n-n)!
    = n! - n!/1! + n!/2! + ... ± (-1)n
    (where nCk is the number of ways of choosing k outcomes out of n possibilities, ignoring order.)
    Therefore, the probability that A wins is d(52) / 52! = 1 - 1/1! + 1/2! - 1/3! + ... + 1/52!

    Note that this expression is the first 53 terms of the Maclaurin series for e-1. The series converges very rapidly to 1/e; the above probability is within 1/53! 2.34×10-70 of 1/e. Therefore, somewhat surprisingly, for any reasonably large number of cards, say, 10 or more, the probability that A wins is almost independent of the number of cards in the decks.


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
About us
Applying for a job can be a stressful and frustrating experience, especially for someone who has never done it before. Considering that you are competing for the position with a at least a dozen other applicants, it is imperative that you thoroughly prepare for the job interview, in order to stand a good chance of getting hired. That's where GeekInterview can help.
Interact