BrainDen.com - Brain Teasers
• 0

# Card Counting

## Question

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?

## Recommended Posts

• 0

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 252:

p = 1/13 (1 + a/252)

My estimate was a = 12 x 213, giving a correction factor a/252 of about 10-11.

Using the generating function described in hints given by BMAD,

a smaller value is found: a = 12 x 24, 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...

##### Share on other sites

• 0

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

##### Share on other sites

• 0

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

##### Share on other sites

• 0

There are 213 = 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 226 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 2n. Here are the distributions for a deck with seven cards/suit, having one, two, three and four suits:

27 = 128 = 20 + 6x18 p = 20/128 = 1/6.4...

214 = 16384 = 2344 + 6x2340; p = 2344/16384 = 1/6.9897...

221 = 2097172 = 299600 + 6x299592; p = 299600/2097172 = 1/6.999906...

228 = 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 252, which is of the order of 1015, divide that number by 13, which is the number of possible remainders, and find a nearby integer n such that n + 12(n-16) = 252.

Then the probability of divisibility by 13 is p = n/252. 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.).

##### Share on other sites

• 0

There are 213 = 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 226 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 2n. Here are the distributions for a deck with seven cards/suit, having one, two, three and four suits:

27 = 128 = 20 + 6x18 p = 20/128 = 1/6.4...

214 = 16384 = 2344 + 6x2340; p = 2344/16384 = 1/6.9897...

221 = 2097172 = 299600 + 6x299592; p = 299600/2097172 = 1/6.999906...

228 = 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 252, which is of the order of 1015, divide that number by 13, which is the number of possible remainders, and find a nearby integer n such that n + 12(n-16) = 252.

Then the probability of divisibility by 13 is p = n/252. 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.

##### Share on other sites

• 0

Let's ask what the answer is for the spade suit alone.There are 213 = 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 226 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 2n. Here are the distributions for a deck with seven cards/suit, having one, two, three and four suits: 27 = 128 = 20 + 6x18 p = 20/128 = 1/6.4...214 = 16384 = 2344 + 6x2340; p = 2344/16384 = 1/6.9897...221 = 2097172 = 299600 + 6x299592; p = 299600/2097172 = 1/6.999906...228 = 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 252, which is of the order of 1015, divide that number by 13, which is the number of possible remainders, and find a nearby integer n such that n + 12(n-16) = 252. Then the probability of divisibility by 13 is p = n/252. 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.

##### Share on other sites

• 0

consider the generating function : f(x) = (1 + x)4(1 + x2)4...(1 + x13)4 = a0 + a1x + a2x2 ... + a364x364

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 = a0 + a13 + ... + a364.

##### Share on other sites

• 0

The exact probability of the sum being 0 mod 13 is

1353275446583/17592186044416 which is approximately 1/12.99970829208
##### Share on other sites

• 0

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) = a0 + a1 + a2 + ... + a13 + a14 + ... + a363 + a364 f(w) = a0 + a1w + a2w2 + ... + a13 + a14w + ... + a363w12 + a364 f(w2) = a0 + a1w2 + a2w4 + ... + a13 + a14w2 + ... + a363w11 + a364 f(w3) = a0 + a1w3 + a2w6 + ... + a13 + a14w3 + ... + a363w10 + a364 ... f(w12) = a0 + a1w12 + a2w11 + ... + a13 + a14w12 + ... + a363w + a364

Since w is a primitive root of unity, the set of values {wk, (wk)2, ... , (wk)12} is a permutation of {w, w2, ... , w12}, for any integer k not divisible by 13.
Therefore, adding these 13 equations, we obtain
f(1) + f(w) + ... + f(w12) = 13(a0 + a13 + ... + a364).
Hence S = [f(1) + f(w) + ... + f(w12)]/13.

##### Share on other sites

• 0

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 = 252 = 4 503 599 627 370 496 = z + 12(z - 213)

z = 346 430 740 566 331

p = z/n = 0.07692307692475597 = 1/12.99999999971624

##### Share on other sites

• 0

The exact probability of the sum being 0 mod 13 is

676644665359/8796093022208 which is approximately 1/12.99957492097
##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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 513 possible ways of
chosing cards from each card value. Now 513 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 252.
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

##### Share on other sites

• 0

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

13 possible ways ofchosing cards from each card value. Now 513 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 252.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.

##### Share on other sites

• 0

the probability that the total value is divisible by 13 is S/252

from the other hints you should be able to find S

##### Share on other sites

• 0

the probability that the total value is divisible by 13 is S/252

from the other hints you should be able to find S

##### Share on other sites

• 0

Putting the above results together, we obtain S = (252 + 12ยท24)/13.

Therefore, the probability that the total value is divisible by 13 is S/252 =

equivalent to: 1/12.999999999999445776666107145483

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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 :-)

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
• ### Recently Browsing   0 members

×

• #### Activity

• Riddles
×
• Create New...