Can You Win the Collaborative Card Game?

You and a friend each shuffle a standard $52$-card deck. You both turn cards over one at a time, in step. If at any position your card exactly matches your friend’s card, you both lose; if you get through all $52$ positions with no coincidence, you both win. What is the probability you win?

The Fiddler, Zach Wissner-Gross, April 19, 2024(original post)

Solution

Hold your own deck fixed as the reference order $1,2,\dots,52$. Your friend’s deck is then a uniformly random permutation $\sigma$ of those cards, and a coincidence at position $i$ means $\sigma(i)=i$, a fixed point. You win exactly when $\sigma$ has no fixed point, that is when $\sigma$ is a derangement. The fraction of permutations with no fixed point is the classic derangement count, $$\frac{D_{52}}{52!}=\sum_{k=0}^{52}\frac{(-1)^k}{k!}\to\frac1e,$$ the alternating series already converged far past anything $52$ cards could resolve. So the win probability is $$\boxed{\dfrac{D_{52}}{52!}}\approx0.3679.$$

The computation

Play the game rather than the formula: draw a random permutation for the friend’s deck, check whether any position is a fixed point, and repeat. The win frequency settles near $1/e$.

import numpy as np
rng = np.random.default_rng(0)
ar = np.arange(52); N = 2_000_000; chunk = 100_000; wins = 0
for _ in range(N // chunk):
    P = rng.random((chunk, 52)).argsort(1)          # random permutations
    wins += (P != ar).all(1).sum()                  # no card sits in its own slot
print(wins / N)                                     # ~0.3679

Extra Credit

Now combine both decks into one pile of $104$ cards, shuffle, and deal it back into two $52$-card decks, one each. Play the same game. What is the probability you win?

Solution

Each of the $52$ kinds of card now appears twice among the $104$. After the shuffle and re-deal, you lose exactly when some kind lands in the same position in both decks. Counting the deals with no such collision by inclusion–exclusion over which positions hold a matched pair gives $$P(\text{win})=\frac{2^{52}}{104!}\sum_{k=0}^{52}(-1)^k\binom{52}{k}\frac{52!}{(52-k)!}\,\frac{(104-2k)!}{2^{52-k}},$$ which comes to $$\boxed{P(\text{win})\approx0.6036.}$$ Pooling and re-dealing nearly doubles your chances, from $37\%$ to $60\%$: every card now has a twin, and the only way to lose is for a pair to be split into the very same slot, which is comparatively rare.

The computation

Again play it: build $104$ cards as two copies of each kind, shuffle, split into two $52$-card decks, and check for a position where both decks show the same kind.

import numpy as np
rng = np.random.default_rng(0)
kinds = np.repeat(np.arange(52), 2)                 # 104 cards, two of each kind
N = 2_000_000; chunk = 100_000; wins = 0
for _ in range(N // chunk):
    deck = kinds[rng.random((chunk, 104)).argsort(1)]
    A, B = deck[:, :52], deck[:, 52:]
    wins += (A != B).all(1).sum()                   # no position matches
print(wins / N)                                     # ~0.6036