## Poll

1 vote (33.33%) | |||

1 vote (33.33%) | |||

1 vote (33.33%) | |||

No votes (0%) | |||

3 votes (100%) | |||

No votes (0%) | |||

2 votes (66.66%) | |||

1 vote (33.33%) | |||

1 vote (33.33%) | |||

1 vote (33.33%) |

**3 members have voted**

Axel and Bob each have his own 52-card deck. Both shuffle them randomly. They then turn over one card at a time, simultaneously, from each deck. What is the probability that they turn over the same card at the same time at least once?

It would be easy to simulate this one or even answer via the Poisson estimation. However, for full credit, I'm looking to see an exact expression of the answer.

As usual, please put answers and solution in spoiler tags.

Free beer to the first satisfactory solution. I ask that those already owed a beer not submit their answers/solutions for at least 48 hours from the time of this post, to give others a chance at the beer.

I am asking because...

the answer appears to be the number of ways to partition the set {1, 2, 3, ..., 52} into partitions all of which are size 2 or larger

Here's why:

The order of Axel's deck doesn't matter, since we are only interested in matches, so assume it's {1, 2, 3, 4, ..., 52}

Bob's deck can be expressed as a set of chains - for example, if the first card is 6, the sixth card is 22, and the 22nd card is 1, then {1, 6, 22} is a chain.

It is possible for all 52 cards to be a single chain.

If any chain of length 1 exists, then that card is in the same position in both decks.

I am under the impression that there is no "closed form" solution to count the number of ways to partition a set of size, say, 52, much less to count the number of ways where there are no partitions of size 1.

However, a quick check of the Online Encyclopedia of Integer Sequences says that the number of partitions is the 53rd term of the recursive sequence:

s

_{n}= n s

_{n-1}+ (-1)

^{n}, where s

_{1}= 0

The probability would be s

_{53}/ 52!

Quote:ThatDonGuyIs there a known, non-brute-force, answer?

Note that I just asked for an exact expression of the answer. The expression can involve functions like summation symbols. Ultimately, I'd like to a way to get at the answer with just the four main operators: +, -, *, and /.

As a reminder, I believe you've won a beer in the last year, so ask you to refrain from further comment until 24 hours after the post.

In that case the answer would be:

1 - 1/e = ~ 63.2 %

Quote:Ace2My guess

Sounds like a derangement problem.

In that case the answer would be:

1 - 1/e = ~ 63.2 %

Quote:TomGJust a guess, but given the warning against simulations, this answer seems too easy:

1 - (51/52)^52 = 63.6%

Much like Ace2, a pretty good estimate, but not the exact answer. There is an effect of removal you must consider.

My initial “estimate” of 1 - 1/e comes out to ~63.2120558828558%.

computers can do this in no time

pari/gp calculator

gp > a=sum(i=1,52,(-1)^(i+1)/i!);

gp > aDec=1.*a;

gp > a

%3 = 333239808909468890675694068318655265019682314241643033726180828783/527177615496365219422618541545122659969212453861982208000000000000

gp > aDec

%4 = 0.63212055882855767840447622983853913255

As ThatDonGuy pointed, we can assume cards are numbered and deck A is ordered A1 = 1, A2 = 2 .. A52 = 52.

Then the probability is the number of orders for deck B for which no card Bi = i divided by the total number of possible orderings, 52!

After a quick search that number is called subfactorial, !52.

So p = !52/52!

!52 = 52! - 52!/1! + 52!/2! - 52!/3! + 52!/4! ...

or !52 = 52! * sum[for n=0 to 52]( -1^n / n!)

Interesting result is that seems to tend to "1/e"

lim !n/n! = 1/e

so !52/52! = 0.3678794411

I did some googling and it's an interesting concept.

https://en.wikipedia.org/wiki/Derangement

In particular that page gives and example of considering giving hats to people and derives the function using a form of recursion. It also gives the answer, which I won't repeat here (near reference (4) ).

So the hint is to see if you can look at the hats problem and derive a recursion.

Quote:7crapsThis math question is quite an old one

computers can do this in no time

pari/gp calculatorsum(i=1,52,(-1)^(i+1)/i!)gp > a=sum(i=1,52,(-1)^(i+1)/i!);

gp > aDec=1.*a;

gp > a

%3 = 333239808909468890675694068318655265019682314241643033726180828783/527177615496365219422618541545122659969212453861982208000000000000

gp > aDec

%4 = 0.63212055882855767840447622983853913255

That is the correct answer!

For the beer, I'd like to see a solution -- an explanation of why it is right.

Quote:tyler498Gotta say I did some practice with 4 or 5 cards before figuring out the concept

As ThatDonGuy pointed, we can assume cards are numbered and deck A is ordered A1 = 1, A2 = 2 .. A52 = 52.

Then the probability is the number of orders for deck B for which no card Bi = i divided by the total number of possible orderings, 52!

After a quick search that number is called subfactorial, !52.

So p = !52/52!

!52 = 52! - 52!/1! + 52!/2! - 52!/3! + 52!/4! ...

or !52 = 52! * sum[for n=0 to 52]( -1^n / n!)

Interesting result is that seems to tend to "1/e"

lim !n/n! = 1/e

so !52/52! = 0.3678794411

Not to say anything is wrong in your post, but your p is the probability that there is NOT a common card.

The following solution is just rewording what others have said. However, I hope the elaboration will be helpful to some.

It is easier to see the logic if we assume the decks are each consist of cards numbered 1 to 52. The first deck is in order, from 1 to 52. The second deck is randomly shuffled. The answer will be the ratio of the number of ways the second deck can be ordered where there is at least one card that matches to the total number of ways to order 52 cards.

Step 1: To start, consider the number of ways the second deck can be ordered where the first card is number 1. The answer is the number of ways to order the other 51 cards, which is 51! = 1551118753287382280224243016469303211063259720016986112000000000000.

Any card can match the first deck, so we must do this for all 52 cards. This gives us 52*51! = 52! combinations where at least one card matches.

Step 2: However, step 1 double counts every situation where two cards match. For example, if the first two cards were 1 and 2, we would have counted the 50! ways to arrange the other cards twice, once for 1 as the first card and a second time for 2 as the second card. The number of ways to choose 2 cards out of 52 is combin(52,2) = 1326. For each combination of two cards, there are 50! = 30414093201713378043612608166064768844377641568960512000000000000 ways to order the other cards. Thus, for step 2 we need to subtract out combin(52,2)*50! = (52*51/2!)*50! = 52!/2! combinations.

Step 3: Next, consider the situation where the first three cards in the random deck are 1, 2, and 3 in order. There are 49! ways to order the other 49 cards. We would have counted them three times in the initial step of counting for at least one matching card. Then we would have subtracted out all combin(3,2)=3 ways to choose 2 out of these three cards in the second step. So this situation would have been counted 3-3=0 times, so we need to add them back in. There are combin(52,3) such situations of choosing at least 3 cards that match. So we need to add back in combin(52,3)*49! = 52*51*50*49!/3! = 52!/3! combinations back in.

Step 4: Next, consider the situation where the first four cards in the random deck are 1, 2, 3, and 4 in order. There are 48! ways to order the other 48 cards. We would have counted them four times in the initial step of counting for at least one matching card. Then we would have subtracted out all combin(4,2)=6 ways to choose two out of these four cards in step 2. Then we would have added all combin(4,3)=4 ways to choose 3 out of these four cards. So we are at 4-6+4=2 ways each such situation would have been counted. So we need to subtract one of those ways out, so that each situation will be counted once. There are combin(52,4)*48! = 52*51*50*49*48!/4! = 52!/4! such situations that need to be added back in.

We will keep doing this, alternating adding and subtracting to correct for double counting.

In the end, the number of situations where at least one card in the random deck matches the ordered deck =

combin(52,1)*51! - combin(52,2)*50! + combin(52,3)*49! - combin(52,4)*48! ... - combin(52,52)*1! =

52!/1! - 52!/2! + 52!/3! - 52!/4! ... - 52!/52! = x = 333239808909468890675694068318655265019682314241643033726180828783.

There are 52! = y = 527177615496365219422618541545122659969212453861982208000000000000 total ways to order 52 cards.

Thus, the answer is x/y = 0.6321205588285576784044762298385391325541888689682321654921631983025382745851401611680269165474009520.

The probability that there are no matches is 1-(x/y) = 0.3678794411714423215955237701614608674458111310317678345078368016974617254148598388319730834525990480.

If this number looks familiar, it should. 1/e = 0.3678794411714423215955237701614608674458111310317678345078368016974614957448998033571472743459196437.

So, the answer can be VERY closely estimated, to 69 decimal places, as 1-(1/e).

Acknowledgements

Mathematical calculations were done in Pari/GP

Yes, 1-1/e is probably accurate to around 50 decimal places.Quote:Wizard[spoiler=Wiz solution]So, the answer can be VERY closely estimated as 1-(1/e).

Quote:Ace2Yes, 1-1/e is probably accurate to around 50 decimal places.Quote:Wizard[spoiler=Wiz solution]So, the answer can be VERY closely estimated as 1-(1/e).

Let's see. With Pari/GP we can get up to 100 significant digits. That gives us:

1/e = 0.3678794411714423215955237701614608674458111310317678345078368016974614957448998033571472743459196437

The answer to the problem at hand is 0.3678794411714423215955237701614608674458111310317678345078368016974617254148598388319730834525990480.

So the estimate is correct to 69 decimal places.

I only have excel so I guess I’m content with only 16 digits. However, when I use https://www.integral-calculator.com/ it will give far more than 16 digits when an integer solution is available.

does "This is great stuff" equal "This is great"Quote:WizardThis is great stuff!

some other sites pointed out the short cut and that the probability is almost the same for any size deck of cards.

at least it converges quickly

#cards - each deck size | prob at least one match | decimal |
---|---|---|

1 | 1 | 1 |

2 | 1/2 | 0.5 |

3 | 2/3 | 0.667 |

4 | 5/8 | 0.625 |

5 | 19/30 | 0.633 |

6 | 91/144 | 0.631944 |

7 | 177/280 | 0.632142857 |

8 | 3641/5760 | 0.632118056 |

9 | 28673/45360 | 0.632120811 |

10 | 28319/44800 | 0.632120536 |

11 | 2523223/3991680 | 0.632120561 |

52 | … | 0.632120559 |

that should lead to the next question of

What is the probability of exactly one card that matches (not at least 1)

Quote:7crapsthat should lead to the next question of

What is the probability of exactly one card that matches (not at least 1)

It would be easy to say the estimate is 1/e, the same as the probability of zero matches. Simple Poisson distribution estimate. Forgive me if I don't put it in exact form.

So basically a fair bet if Axel takes an odd number of matches and Bob takes an even number of matches (including 0)?Quote:WizardIt would be easy to say the estimate is 1/e, the same as the probability of zero matches. Simple Poisson distribution estimate. Forgive me if I don't put it in exact form.

The exact probability of zero matches is the sum from m=0 to m=52 of (-1)^m / m!. Call that probability Z. As we already know, Z will be very close to 1/e, accurate to nearly 70 digits.Quote:7crapsthat should lead to the next question of

What is the probability of exactly one card that matches (not at least 1)

The exact probability of one match should be Z minus 1/52!

Quote:unJonSo basically a fair bet if Axel takes an odd number of matches and Bob takes an even number of matches (including 0)?

The even number of matches would be favored. 0 and 1 cancel each other out. For x>=1, pr(x matches) >= pr(x+1 matches).