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

Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1336
  • Posts: 22046
January 2nd, 2020 at 5:39:43 PM permalink
We haven't had a good math puzzle in a while. What better way to welcome in 2020 than sharpening our math skills with some good problems?!

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.
It's not whether you win or lose; it's whether or not you had a good bet.
sodawater
sodawater
Joined: May 14, 2012
  • Threads: 64
  • Posts: 3321
January 2nd, 2020 at 5:51:51 PM permalink
No idea how to do the math, but I know this is like a 100-year-old bar hustle and the side betting on a match has a big edge.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 95
  • Posts: 4332
January 2nd, 2020 at 6:51:59 PM permalink
Is there a known, non-brute-force, answer?

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:
sn = n sn-1 + (-1)n, where s1 = 0
The probability would be s53 / 52!

Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1336
  • Posts: 22046
January 2nd, 2020 at 7:47:25 PM permalink
Quote: ThatDonGuy

Is 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.
It's not whether you win or lose; it's whether or not you had a good bet.
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 21
  • Posts: 705
January 2nd, 2020 at 7:48:09 PM permalink
My guess

Sounds like a derangement problem.

In that case the answer would be:

1 - 1/e = ~ 63.2 %
It’s all about making that GTA
TomG
TomG
Joined: Sep 26, 2010
  • Threads: 13
  • Posts: 2077
January 2nd, 2020 at 8:54:37 PM permalink
Just a guess, but given the warning against simulations, this answer seems too easy:

1 - (51/52)^52 = 63.6%
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1336
  • Posts: 22046
January 2nd, 2020 at 9:18:06 PM permalink
Quote: Ace2

My guess

Sounds like a derangement problem.

In that case the answer would be:

1 - 1/e = ~ 63.2 %



That would be a good estimate of the answer, but not an exact form. Certainly the answer is an integer divided by an integer, thus the answer must be rational, unlike your estimate.
It's not whether you win or lose; it's whether or not you had a good bet.
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1336
  • Posts: 22046
January 2nd, 2020 at 9:19:11 PM permalink
Quote: TomG

Just 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.
It's not whether you win or lose; it's whether or not you had a good bet.
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 21
  • Posts: 705
January 2nd, 2020 at 9:27:30 PM permalink
My 2nd guess

The sum of (-1)^(j+1)/j! from j=1 to j=52 which is ~63.2120558828558%.

My initial “estimate” of 1 - 1/e comes out to ~63.2120558828558%.
Last edited by: Ace2 on Jan 2, 2020
It’s all about making that GTA
7craps
7craps
Joined: Jan 23, 2010
  • Threads: 18
  • Posts: 1977
January 2nd, 2020 at 10:43:32 PM permalink
This math question is quite an old one
computers can do this in no time
pari/gp calculator
sum(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
winsome johnny (not Win some johnny)

  • Jump to: