Shuffle a deck of cards, then deal one card at a time, counting off "Ace, deuce, ...
probability/card/counting.match
Problem
Shuffle a deck of cards, then deal one card at a time, counting off "Ace, deuce, ... King, Ace, deuce, ..." etc. If you deal a card matching the card you just said, you lose. If you deal out all the cards (without losing, of course) you win. What is the probability of winning? -- James Layland <jlayland@kilroy.Jpl.Nasa.Gov>, December 1993
Show solution
The chance of winning with a 52-card deck is exactly
4610507544750288132457667562311567997623087869
------------------------------------------------ = 0.01623272746...
284025438982318025793544200005777916187500000000
or about 1 game in 61.6. This game is known as "Frustration Solitaire";
the value 0.01623... is given by Peter G. Doyle, Charles M. Grinstead
and J. Laurie Snell in their paper "Frustration Solitaire" (1995).
Method: inclusion-exclusion with rook polynomials. Lay the 52 deal
positions against the 52 cards. Position j is "forbidden" for the four
cards of the rank called at j. The forbidden cells form 13 disjoint
4 x 4 blocks (the 4 positions where a rank is called, times the 4 cards
of that rank). Let r_k be the number of ways to choose k forbidden
cells, no two in the same row or column. For one 4 x 4 block the
counts are C(4,j)^2 j! for j = 0..4, that is 1, 16, 72, 96, 24, so
R(x) = sum r_k x^k = (1 + 16x + 72x^2 + 96x^3 + 24x^4)^13,
and by inclusion-exclusion the number of winning deals is
W = sum over k of (-1)^k r_k (52 - k)!.
The probability is W / 52!. A C++ program (exact integer arithmetic
with GMP) gives the fraction above, with
W = 13093021755511771629310450002599225253087634
33362019257020678406144
(one 67-digit number) winning orders out of 52!.
The same program reproduces the small cases in David Karr's reply
below: 2 suits of 2 ranks (4 cards) gives 1/6, 4 suits of 2 ranks
(8 cards) gives 576/40320 = 1/70, and one suit of 3 cards gives 1/3.
For a single suit of n cards it is the classical derangement number,
probability 1 - 1/1! + 1/2! - ... +/- 1/n!.
The formula (1 - s/n)^n proposed below is not exact (it treats the 52
positions as independent), and for 4 suits of 13 it gives 0.01557
against the true 0.01623. But the limit David Karr asked about is
right: with s suits and the number of ranks growing, the chance of
winning tends to e^(-s), here e^(-4) = 0.0183. The true value 0.0162
is a little smaller because of the finite number of ranks.
-- Claude (rec.puzzles Oracle, 2026-11-02)
[ Editor: the material collected earlier follows. ]
[ Editor: the collected reply corrects a proposed answer but gives no
exact value for the 52-card deck. For a single suit (all cards
different) see probability/derangement. ]
In article <CHpJ7E.HG0@news.chalmers.se> lubin@fy.chalmers.se replies:
>For a single suit, that is if each card is uniquely labelled, the
>probability of losing on a given card is 1/n. The probability of not
>losing on all of them is:
>
>(1-(1/n))^n which approaches exp(-1)=0.3688 for large n.
[ Editor: exp(-1) = 0.3679. ]
Try a few small cases:
If n = 2, the probability of no match is 1/2 (overall).
(1 - (1/n))^n = (1/2)^2 = 1/4, incorrect.
If n = 3, there are six possible permutations, of which only two have
no match (by inspection). The probability of no match then is 1/3
overall. (1 - (1/n))^n = (2/3)^3 = 8/27, incorrect.
The actual probability of not matching exactly on any of n cards is
p_n = 1 - 1/1! + 1/2! - 1/3! + - ... +/- 1/n!
which is a truncated Taylor series expansion of f(x) = e^x centered at
0 and evaluated at x = -1.
For n = 2, p_n = 1 - 1 + 1/2 = 1/2, correct.
For n = 3, p_n = 1 - 1 + 1/2 - 1/6 = 1/3, correct.
In other words you have the wrong p_n, though it has the right limit.
>(1-(s/n))^n
>
>is exact for a pack of n cards divided into s suits.
Test cases:
For s = 1, we already found this formula incorrect.
For s = 2, n = 4, there are 24 ways to deal 4 cards. By inspection
only 4 of these have no matches, so the probability is 1/6.
(1 - (s/n))^n = (1/2)^4 = 1/16, incorrect.
For s = 4, n = 8, there are 8! = 40320 ways to deal the cards, and only
(4!)^2 = 576 have no matches. The probability is 1/70.
(1 - (s/n))^n = (1/2)^8 = 1/256, incorrect.
The limiting case e(-s) may be correct, I don't know. But I don't
think (1 - 1/13)^52 is the exact answer to the original question.
-- David A. Karr <karr@cs.cornell.edu>
[ Editor: the rest of Dror Lubin's reply, part of which is quoted in
the entry above. ]
Now if you have s suits, the probability of losing on a SPECIFIC card
is s/n. The probability of not losing on all of them is:
(1-(s/n))^n which approaches exp(-s) for large n.
Substitute s=4, n=52 we find the exact probability:
(1-(1/13))^52 = 0.01557, like you have computed empirically. This is
slightly smaller than exp(-4)=0.01832 which is the limiting value for 4
suits, many cards in each. In any case, the formula:
(1-(s/n))^n
is exact for a pack of n cards divided into s suits.
-- Dror Lubin <lubin@fy.chalmers.se>, December 1993
[ Editor: the formula is not exact; see David Karr's test cases in the
entry above, e.g. s = 2, n = 4 gives 1/6, not (1/2)^4 = 1/16. ]