# Solution to puzzle 26: Two packs of cards

Players A and B 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 A wins if, once the packs are fully dealt, no matches are found. Player B wins if at least one match occurs. What is the probability that player A wins?

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 (a_{1}, a_{2}, ... , a_{52}) for which a_{i} 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 a_{i} = i) |

| + sum over distinct i, j (number of deals for which a_{i} = i and a_{j} = j) |

| − sum over distinct i, j, k (number of deals for which a_{i} = i, a_{j} = j and a_{k} = k) |

| ± number of ways in which a_{i} = 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! − _{n}C_{1} · (n−1)! + _{n}C_{2} · (n−2)! + ... ± _{n}C_{n} · (n−n)! |

| = n! − n!/1! + n!/2! + ... ± (−1)^{n} |

(where

_{n}C_{k} 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.

## Further reading

- Derangements and Applications
- Online Encyclopedia of Integer Sequences: A000166

Source: Traditional

Back to top