Can You Win the Collaborative Card Game?

This Week's Fiddler

If we pair up each card from one 52-card deck with another, we lose if any of them in the same position match. In other words, we win if one deck is a derangement of the other!

Let $!n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$ denote the $n$-th derangement number (also known as the $n$-th subfactorial). There are $!52$ derangements of the deck out of $52!$ possible permutations of the deck.

Thus, the chance of winning is $\frac{!52}{52!}=\sum_{k=0}^{52}\frac{(-1)^k}{k!}$. This comes out to $\frac{193937806586896328746924473226467394949530139620339174273819171217}{527177615496365219422618541545122659969212453861982208000000000000}$, or about 36.79%.

Answer: (!52)/(52!), or ~36.79% (193937806586896328746924473226467394949530139620339174273819171217/527177615496365219422618541545122659969212453861982208000000000000)

Extra Credit

In this version of the game, we're combining the decks, shuffling the cards, and forming card pairs, hoping to never get a matching pair.

Let $p$ be the number of matching pairs left, let $s$ be the number of unmatched (single) cards left, and let $f(p, s)$ be the probability we win given $p$ matching pairs of cards and $s$ unmatched cards left in the deck.

If there are no cards left, then we have won, so $f(0, 0) = 1$. Also, $p$ and $s$ should never be negative, so $f(p, s) = 0$ if $p\lt0$ or $s\lt0$. Otherwise, let's consider the three successful events with drawing two cards: ($A$) two cards are chosen from different pairs, ($B$) one card is chosen from a pair and one is a single, or ($C$) both cards are singles.

$$P(A) = \frac{2p}{2p+s} \cdot \frac{2(p-1)}{2p+s-1} = \frac{4p(p-1)}{(2p + s)(2p + s - 1)} \\ P(B) = 2! \cdot \frac{(2p)(s)}{(2p+s)(2p + s - 1)} = \frac{4ps}{(2p + s)(2p + s - 1)} \\ P(C) = \frac{s}{2p+s} \cdot \frac{s-1}{2p+s-1} = \frac{s(s-1)}{(2p + s)(2p + s - 1)}$$

(Note: We can also confirm that the probability that we lose, meaning a match is of the same pair, is $\frac{2p}{(2p + s)(2p + s - 1)}$, adding up with $P(A)$, $P(B)$, and $P(C)$ to make 1. These four events are thus exhaustive possibilities.)

For $A$, we convert two pairs into two unmatched singles, so the next step is $f(p - 2, s + 2)$. For $B$, we convert one pair into an unmatched single but also consume a different unmatched single, netting in zero change to the number of singles and making the next step $f(p - 1, s)$. For $C$, we simply consume two unmatched singles: $f(p, s - 2)$.

Putting it all together then, when $p\ge0$ and $s\ge0$ and at least one of $p$ or $s$ is positive:

$$f(p, s) = f(p - 2, s + 2) \cdot \frac{4p(p-1)}{(2p + s)(2p + s - 1)} + f(p - 1, s) \cdot \frac{4ps}{(2p + s)(2p + s - 1)} + f(p, s - 2) \cdot \frac{s(s-1)}{(2p + s)(2p + s - 1)}$$

Now that we have a recursive formula defined, we can convert it into Python code (with dynamic programming to cache results):

from functools import cache


@cache
def prob(pairs=52, singles=0):
    if pairs < 0 or singles < 0:
        return 0
    if pairs == 0 or singles == 0:
        return 1

    total = pairs * 2 + singles
    return (
        # Two cards from different pairs
        prob(pairs - 2, singles + 2) * Fraction(4 * pairs * (pairs - 1), total * (total - 1))
        # One card from a pair and one single
        + prob(pairs - 1, singles) * Fraction(4 * pairs * singles, total * (total - 1))
        # Two singles
        + prob(pairs, singles - 2) * Fraction(singles * (singles - 1), total * (total - 1))
    )


print(prob())
print(float(prob()))

Output:

335561727225862936774353972738829595013743745454800896090990716254443717947031552/555926557447585078813889409645210912590669690718980253197612210789777133544921875
0.6036080175167761

Looks like our odds have improved to $\frac{335561727225862936774353972738829595013743745454800896090990716254443717947031552}{555926557447585078813889409645210912590669690718980253197612210789777133544921875}$, or about 60.36%.

Answer: ~60.36% (335561727225862936774353972738829595013743745454800896090990716254443717947031552/555926557447585078813889409645210912590669690718980253197612210789777133544921875)

Simulation

Python simulation code to check my work:

import random

N = 52
T = 10**7


# This Week's Fiddler

random.seed(12)
total = 0
deck1 = list(range(N))
deck2 = list(range(N))

for _ in range(T):
    random.shuffle(deck1)
    random.shuffle(deck2)
    total += all(a != b for a, b in zip(deck1, deck2))

print('Part 1 simulated probability:', total / T)


# Extra Credit

random.seed(12)
total = 0
deck = list(range(N)) + list(range(N))

for _ in range(T):
    random.shuffle(deck)
    total += all(a != b for a, b in zip(deck[:N], deck[N:]))

print('Part 2 simulated probability:', total / T)

Output:

Part 1 simulated probability: 0.3678149
Part 2 simulated probability: 0.6032972