Skip to main content.

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 (a1, a2, ... , a52) for which ai not equal to 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! is approximately equal to 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

  1. (Adobe) Portable Document Format Derangements and Applications
  2. Online Encyclopedia of Integer Sequences: A000166

Source: Traditional

Back to top