Card Counting

[BMAD]

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?

[bonanova]

It is clear that the probability is greater than 1/13 by a small amount.

I considered decks small enough to enumerate. I noticed a pattern in the excess numbers of cases that were divisible by 13. I chose a single and double suited deck with 13 cards per suit, and a smaller deck that had 7 cards per suit, and one, two, three, and four suits. This led to a simple function for the excess cases that had zero remainder when divided by 13 (or in the second case by 7), and an equal number of cases for each non-zero remainder.

When I later looked at single-suited decks with 2 to 20 cards per suit, the simple relationship no longer held. It turns out that each prime factor of outcomes behaved regularly. Seven cards per suit was predictable, but fourteen cards exhibited the seven card pattern twice. So I knew the simple formula gave too high a result. But I was not able to figure out, precisely what it was. Even though it was too large, it was dwarfed by all the other numbers, so my result of "very slightly greater than 1/13" was accurate.

The general formula for the probability involves a term a, which represents the excess number of cases for exact divisibility by 13, and which is very very much smaller than 2⁵²:

p = 1/13 (1 + a/2⁵²)

My estimate was a = 12 x 2¹³, giving a correction factor a/2⁵² of about 10^-11.

Using the generating function described in hints given by BMAD,

a smaller value is found: a = 12 x 2⁴, giving a correction factor of about 10^-14.

Thus, in summary,

My value:

p = 0.076 923 076 924 755 97... = 1/12.999 999 999 716 24...

Generating-function value:

p = 0.076 923 076 923 080 20 ... = 1/12.999 999 999 999 44...

[k-man]

Roughly 1/13.

The total value of cards facing up will be between 0 and 364. Even though the probability of each outcome is different the probabilities form a bell curve, but we're only concerned with 13 different outcomes that are derived by taking the remainder from the division of the total value by 13. Those 13 different outcomes have approximately the same probability of occurring

[BMAD]

I am extremely tempted to mark your answer solved. It is very close. I never looked at the approach like that before for this problem. It gives a very very good approximation one that you have to go out about 8 decimal places to see a difference. I will wait and see if someone can find the more precise answer.

Roughly 1/13.

The total value of cards facing up will be between 0 and 364. Even though the probability of each outcome is different the probabilities form a bell curve, but we're only concerned with 13 different outcomes that are derived by taking the remainder from the division of the total value by 13. Those 13 different outcomes have approximately the same probability of occurring

[bonanova]

Let's ask what the answer is for the spade suit alone.

There are 2¹³ = 8192 up-card configurations, and I just counted the card values for each of them. In 632 cases the total was a multiple of 13.

p = 0.0771484375 = 1/12.96702532.

Fairly close to 1/13. I went back and got the count for the 12 other remainders. It was 630 in every other case. There was an excess of 2 cases for exact multiples. That is, 632 + 12x630 = 8192 cases. So now I am curious about more suits in the deck.

I added hearts to the spades and counted remainders for those 2²⁶ cases. It turned out that the zero remainder cases outnumbered the others by 4. But there were astronomically more cases, making that small excess really insignificant. So for a deck comprising hearts and spades we get

p = 1/12.9999907.

The only question remaining for adding diamonds and clubs is whether the excess numbers for zero remainder would be 6 and 8, or 8 and 16. The numbers were getting too large, so I tried a deck with only seven cards to a suit and checked for divisibility by seven. I could enumerate 3 and 4 suit decks. It turns out the excess number for an n-suited deck is 2ⁿ. Here are the distributions for a deck with seven cards/suit, having one, two, three and four suits:

2⁷ = 128 = 20 + 6x18 p = 20/128 = 1/6.4...

2¹⁴ = 16384 = 2344 + 6x2340; p = 2344/16384 = 1/6.9897...

2²¹ = 2097172 = 299600 + 6x299592; p = 299600/2097172 = 1/6.999906...

2²⁸ = 268435456 = 38347936 +6x38347920; p = 38347936/268435456 = 1/6.99999749...

This validates the analysis. Note that the red numbers differ by 2, 4, 8 and 16 for 1, 2, 3 and 4 suits.

So back to the 13-card per suit deck. The calculation procedure is to take the number of up-card configurations, in our case that's 2⁵², which is of the order of 10¹⁵, divide that number by 13, which is the number of possible remainders, and find a nearby integer n such that n + 12(n-16) = 2⁵².

Then the probability of divisibility by 13 is p = n/2⁵². This is approximately

p = 1/12.99999999999999...

where there are 14 '9's (1 less than the exponent of 10 for the number of configurations.).

[BMAD]

Let's ask what the answer is for the spade suit alone.

There are 2¹³ = 8192 up-card configurations, and I just counted the card values for each of them. In 632 cases the total was a multiple of 13.

p = 0.0771484375 = 1/12.96702532.

Fairly close to 1/13. I went back and got the count for the 12 other remainders. It was 630 in every other case. There was an excess of 2 cases for exact multiples. That is, 632 + 12x630 = 8192 cases. So now I am curious about more suits in the deck.

I added hearts to the spades and counted remainders for those 2²⁶ cases. It turned out that the zero remainder cases outnumbered the others by 4. But there were astronomically more cases, making that small excess really insignificant. So for a deck comprising hearts and spades we get

p = 1/12.9999907.

The only question remaining for adding diamonds and clubs is whether the excess numbers for zero remainder would be 6 and 8, or 8 and 16. The numbers were getting too large, so I tried a deck with only seven cards to a suit and checked for divisibility by seven. I could enumerate 3 and 4 suit decks. It turns out the excess number for an n-suited deck is 2ⁿ. Here are the distributions for a deck with seven cards/suit, having one, two, three and four suits:

2⁷ = 128 = 20 + 6x18 p = 20/128 = 1/6.4...

2¹⁴ = 16384 = 2344 + 6x2340; p = 2344/16384 = 1/6.9897...

2²¹ = 2097172 = 299600 + 6x299592; p = 299600/2097172 = 1/6.999906...

2²⁸ = 268435456 = 38347936 +6x38347920; p = 38347936/268435456 = 1/6.99999749...

This validates the analysis. Note that the red numbers differ by 2, 4, 8 and 16 for 1, 2, 3 and 4 suits.

So back to the 13-card per suit deck. The calculation procedure is to take the number of up-card configurations, in our case that's 2⁵², which is of the order of 10¹⁵, divide that number by 13, which is the number of possible remainders, and find a nearby integer n such that n + 12(n-16) = 2⁵².

Then the probability of divisibility by 13 is p = n/2⁵². This is approximately

p = 1/12.99999999999999...

where there are 14 '9's (1 less than the exponent of 10 for the number of configurations.).

The answer is even closer so if no one can find an even more precise answer then this will be the answer. And before I get some guessess with a bunch of nines, the answer that i found is not consisting solely of running nines after the decimal.

[bonanova]

Let's ask what the answer is for the spade suit alone.There are 2¹³ = 8192 up-card configurations, and I just counted the card values for each of them. In 632 cases the total was a multiple of 13. p = 0.0771484375 = 1/12.96702532. Fairly close to 1/13. I went back and got the count for the 12 other remainders. It was 630 in every other case. There was an excess of 2 cases for exact multiples. That is, 632 + 12x630 = 8192 cases. So now I am curious about more suits in the deck. I added hearts to the spades and counted remainders for those 2²⁶ cases. It turned out that the zero remainder cases outnumbered the others by 4. But there were astronomically more cases, making that small excess really insignificant. So for a deck comprising hearts and spades we get p = 1/12.9999907. The only question remaining for adding diamonds and clubs is whether the excess numbers for zero remainder would be 6 and 8, or 8 and 16. The numbers were getting too large, so I tried a deck with only seven cards to a suit and checked for divisibility by seven. I could enumerate 3 and 4 suit decks. It turns out the excess number for an n-suited deck is 2ⁿ. Here are the distributions for a deck with seven cards/suit, having one, two, three and four suits: 2⁷ = 128 = 20 + 6x18 p = 20/128 = 1/6.4...2¹⁴ = 16384 = 2344 + 6x2340; p = 2344/16384 = 1/6.9897...2²¹ = 2097172 = 299600 + 6x299592; p = 299600/2097172 = 1/6.999906...2²⁸ = 268435456 = 38347936 +6x38347920; p = 38347936/268435456 = 1/6.99999749... This validates the analysis. Note that the red numbers differ by 2, 4, 8 and 16 for 1, 2, 3 and 4 suits. So back to the 13-card per suit deck. The calculation procedure is to take the number of up-card configurations, in our case that's 2⁵², which is of the order of 10¹⁵, divide that number by 13, which is the number of possible remainders, and find a nearby integer n such that n + 12(n-16) = 2⁵². Then the probability of divisibility by 13 is p = n/2⁵². This is approximately p = 1/12.99999999999999... where there are 14 '9's (1 less than the exponent of 10 for the number of configurations.).

The answer is even closer so if no one can find an even more precise answer then this will be the answer. And before I get some guessess with a bunch of nines, the answer that i found is not consisting solely of running nines after the decimal.

It would repeat, being rational.

I just tried to investigate its closeness to 1/13.

I'm still thinking about the small excess count for multiples.

[BMAD]

consider the generating function : f(x) = (1 + x)⁴(1 + x²)⁴...(1 + x¹³)⁴ = a₀ + a₁x + a₂x² ... + a₃₆₄x³⁶⁴

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₀ + a₁₃ + ... + a₃₆₄.

[superprismatic]

The exact probability of the sum being 0 mod 13 is

1353275446583/17592186044416 which is approximately 1/12.99970829208

[BMAD]

Express S in terms of f(1), f(w), ... , f(w12)

Let w be a (complex) primitive 13th root of unity. Then w13 = 1 and 1 + w + w2 + ... + w12 = 0. Consider

f(1) = a₀ + a₁ + a₂ + ... + a₁₃ + a₁₄ + ... + a₃₆₃ + a₃₆₄ f(w) = a₀ + a₁w + a₂w² + ... + a₁₃ + a₁₄w + ... + a₃₆₃w¹² + a₃₆₄ f(w²) = a₀ + a₁w² + a₂w⁴ + ... + a₁₃ + a₁₄w² + ... + a₃₆₃w¹¹ + a₃₆₄ f(w³) = a₀ + a₁w³ + a₂w⁶ + ... + a₁₃ + a₁₄w³ + ... + a₃₆₃w¹⁰ + a₃₆₄ ... f(w¹²) = a₀ + a₁w¹² + a₂w¹¹ + ... + a₁₃ + a₁₄w¹² + ... + a₃₆₃w + a₃₆₄

Since w is a primitive root of unity, the set of values {w^k, (w^k)², ... , (w^k)¹²} is a permutation of {w, w², ... , w¹²}, for any integer k not divisible by 13.
Therefore, adding these 13 equations, we obtain
f(1) + f(w) + ... + f(w¹²) = 13(a₀ + a₁₃ + ... + a₃₆₄).
Hence S = [f(1) + f(w) + ... + f(w¹²)]/13.

[bonanova]

My current estimate of bias toward exact multiple is too high.

It is close enough, though, to post the probability it predicts.

I may refine it.

I may also look at the generating function.

Here's an exact expression for my current analysis:

Define these constants:

n = 2⁵² = 4 503 599 627 370 496 = z + 12(z - 2¹³)

z = 346 430 740 566 331

p = z/n = 0.07692307692475597 = 1/12.99999999971624

[superprismatic]

The exact probability of the sum being 0 mod 13 is

676644665359/8796093022208 which is approximately 1/12.99957492097

[BMAD]

Evaluate f(1), f(w), ... , f(w12)

Clearly, from (1), f(1) = 252.

Also, f(w) = [(1 + w)(1 + w2)...(1 + w13)]4.(2)

Consider g(x) = x13 − 1 = (x − w)(x − w2)...(x − w13).

Then g(−1) = −2 = (−1 − w)(−1 − w2)...(−1 − w13).

Hence (1 + w)(1 + w2)...(1 + w13) = 2.

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

Hence f(w) = f(w2) = ... = f(w12) = 2.

[superprismatic]

My approach was to exhaust over all possible outcomes.

Lets look at what can possibly be chosen from a particular
value of card and look at what can happen with the four
7s in the deck. With Probability 1/16, no 7s are chosen
which contributes 0 to the running sum; with probability
4/16, one 7 is chosen which contributes 7 to the running
sum; with probability 6/16, two 7s are chosen which
contributes 1 (mod 13) to the running sum; with probability
4/16, three 7s are chosen which contributes 8 (mod 13)
to the running sum; with probability 1/16, four 7s are
chosen which contributes 2 (mod 13) to the running sum.
So, for the 7s in the deck we have 5 possible contributions
to the mod 13 sum with their respective probabilities.
We can do this with all 13 sets of card values. So, we can
compute the contributions of all 5¹³ possible ways of
chosing cards from each card value. Now 5¹³ is about 1.22
billion ways. We also know the probabilities involved, so
we can compute the probability of each way of forming any
particular mod 13 value. Furthemore, we can do the
calculations with all integer arithmetic by using 1,4,6,4,1
instead of 1/16, 4/16, 6/16, 4/16, 1/16. When we do this,
all the mod 13 counts we get had better add up to 2⁵².
This is a check on the program. I wrote the program and it
takes about 5 seconds to run on my Intel Core7 machine.
The mod 13 sums and counts are as follows:

0 346442068663808
1 346425832982400
2 346393927579136
3 346477138939392
4 346368483871232
5 346474428126848
6 346463204652160
7 346402730352000
8 346453603433856
9 346431886650368
10 346395126293504
11 346461321451008
12 346409874374784
4503599627370496 Total which is 2^52

So, the probability of a sum of 0 (mod 13) is
346442068663808/4503599627370496
which is approximately 1/12.99957492097

[bonanova]

My approach was to exhaust over all possible outcomes.Lets look at what can possibly be chosen from a particularvalue of card and look at what can happen with the four7s in the deck. With Probability 1/16, no 7s are chosenwhich contributes 0 to the running sum; with probability4/16, one 7 is chosen which contributes 7 to the runningsum; with probability 6/16, two 7s are chosen whichcontributes 1 (mod 13) to the running sum; with probability4/16, three 7s are chosen which contributes 8 (mod 13)to the running sum; with probability 1/16, four 7s arechosen which contributes 2 (mod 13) to the running sum.So, for the 7s in the deck we have 5 possible contributionsto the mod 13 sum with their respective probabilities.We can do this with all 13 sets of card values. So, we cancompute the contributions of all 5

¹³ possible ways ofchosing cards from each card value. Now 5¹³ is about 1.22billion ways. We also know the probabilities involved, sowe can compute the probability of each way of forming anyparticular mod 13 value. Furthemore, we can do thecalculations with all integer arithmetic by using 1,4,6,4,1instead of 1/16, 4/16, 6/16, 4/16, 1/16. When we do this,all the mod 13 counts we get had better add up to 2⁵².This is a check on the program. I wrote the program and ittakes about 5 seconds to run on my Intel Core7 machine.The mod 13 sums and counts are as follows:

0 3464420686638081 3464258329824002 3463939275791363 3464771389393924 3463684838712325 3464744281268486 3464632046521607 3464027303520008 3464536034338569 34643188665036810 34639512629350411 34646132145100812 3464098743747844503599627370496 Total which is 2^52

So, the probability of a sum of 0 (mod 13) is346442068663808/4503599627370496which is approximately 1/12.99957492097

Nice. At first blush it looks solid.

Intuitively I'm expecting something closer to 1/13, but it is what the process says it is.

Having just learned generating functions, I'm thinking the gf for this approach might be reasonably straightforward.

[BMAD]

the probability that the total value is divisible by 13 is S/2⁵²

from the other hints you should be able to find S

[bonanova]

the probability that the total value is divisible by 13 is S/2⁵²

from the other hints you should be able to find S

BMAD, for generating-function result, see

[BMAD]

Putting the above results together, we obtain S = (2⁵² + 12·2⁴)/13.

Therefore, the probability that the total value is divisible by 13 is S/2⁵² =

equivalent to: 1/12.999999999999445776666107145483

[superprismatic]

I found a novice programmer mistake in my code which computed the values in

my post #14. The value I get now is the same that bonanova and BMAD get.

I'm relieved that my approach agrees with the concise generating function one.

[BMAD]

I found a novice programmer mistake in my code which computed the values in

my post #14. The value I get now is the same that bonanova and BMAD get.

I'm relieved that my approach agrees with the concise generating function one.

i am too :-)