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

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.