A standard pack of cards is thrown into the air in such a way that each card, independently, is equally likely to land face up or face down. The total value of the cards which landed face up is then calculated. (Card values are assigned as follows: Ace=1, 2=2, ... , 10=10, Jack=11, Queen=12, King=13. There are no jokers.)

What is the probability that the total value is divisible by 13?

There are 2^{52} equally likely configurations of face up/face down. We seek the number of configurations for which the sum of face up card values is divisible by 13.

Consider the generating function

f(x) = (1 + x)^{4}(1 + x^{2})^{4}...(1 + x^{13})^{4} = a_{0} + a_{1}x + a_{2}x^{2} ... + a_{364}x^{364}.(1)

There is a bijection between each card configuration and a contribution to the corresponding term in the generating function. Each exponent in the generating function represents a total score; the corresponding coefficient represents the number of ways of obtaining that score.

Hence we seek the sum S = a_{0} + a_{13} + ... + a_{364}.

Let w be a (complex) primitive 13th root of unity. Then w^{13} = 1 and 1 + w + w^{2} + ... + w^{12} = 0. Consider

f(1) | = a_{0} + | a_{1} + | a_{2} + ... + | a_{13} + | a_{14} + ... + | a_{363} + | a_{364} |

f(w) | = a_{0} + | a_{1}w + | a_{2}w^{2} + ... + | a_{13} + | a_{14}w + ... + | a_{363}w^{12} + | a_{364} |

f(w^{2}) | = a_{0} + | a_{1}w^{2} + | a_{2}w^{4} + ... + | a_{13} + | a_{14}w^{2} + ... + | a_{363}w^{11} + | a_{364} |

f(w^{3}) | = a_{0} + | a_{1}w^{3} + | a_{2}w^{6} + ... + | a_{13} + | a_{14}w^{3} + ... + | a_{363}w^{10} + | a_{364} |

... | |||||||

f(w^{12}) | = a_{0} + | a_{1}w^{12} + | a_{2}w^{11} + ... + | a_{13} + | a_{14}w^{12} + ... + | a_{363}w + | a_{364} |

Since w is a *primitive* root of unity, the set of values {w^{k}, (w^{k})^{2}, ... , (w^{k})^{12}} is a permutation of {w, w^{2}, ... , w^{12}}, for any integer k not divisible by 13.

Therefore, adding these 13 equations, we obtain

f(1) + f(w) + ... + f(w^{12}) = 13(a_{0} + a_{13} + ... + a_{364}).

Hence S = [f(1) + f(w) + ... + f(w^{12})]/13.

Clearly, from (1), f(1) = 2^{52}.

Also, f(w) = [(1 + w)(1 + w^{2})...(1 + w^{13})]^{4}.(2)

Consider g(x) = x^{13} − 1 = (x − w)(x − w^{2})...(x − w^{13}).

Then g(−1) = −2 = (−1 − w)(−1 − w^{2})...(−1 − w^{13}).

Hence (1 + w)(1 + w^{2})...(1 + w^{13}) = 2.

Again, since w is a primitive root of unity, the terms of f(w^{2}), ... , f(w^{12}), will simply be a permutation of those for f(w), in (2).

Hence f(w) = f(w^{2}) = ... = f(w^{12}) = 2.

Putting the above results together, we obtain S = (2^{52} + 12·2^{4})/13.

Therefore, the probability that the total value is divisible by 13 is S/2^{52} =

Torsten Sillke gives a more general solution to the problem that served as the inspiration for this puzzle (see below) in partition probability.

Source: Inspired by problem K 24 in Problems in Elementary Number Theory (problems since taken down)