Matching and Thrown cards

[lostdummy]

I found seemingly simple puzzle on web, something like:

1) Matching cards:
Two players each have deck of 52 cards. After they shuffle them, they draw from the top of the deck one card at a time. If at any draw they get same cards, first player win. If all cards are dealt and no match occurs, second player win. What is probability for second player to win?

Decided to post here because my simple solution did not exactly match posted solution on site where i found it, even if I still do not see what (if anything) was missing from that simple solution ;p

Another one from same place, was something like:
2) Thrown cards:
Deck of 52 cards is thrown in air and each card independently is equally likely to land on face up or down. If you add up values of each card with face up ( where Aces are value 1, 2=2... King=13), what is probability that sum is divisible by 13?

I liked that one because my first simple math idea didnt work, and my first brute force program idea also didn't work (needed 2^52 calculations) ;p

[ralphmerridew]

For problem 2, I get 5412980321359/70368744177664, or a little more than 1/13.

[lostdummy]

Nice. It is same result as what I got, or more precisely:

I had 21647626318140 / 281474976710656, where left side is number of all possible combinations of 48 cards (Ace .. Queen) divisible by 13 (counted by program), while right side is 2^48 (all combinations).

Both sides could be divided by 4 to get exactly your numbers.

But since I got my solution by computer calculation, I would be interested if you got your numbers by math, and if there is any reasonably simple solution ?

[Trojan Horse]

Too tempting to post the answer to #1. But I'll leave it to someone else. (Can't really brag that I know the answer; we discussed this type of problem in one of my math classes this semester.)

[ralphmerridew]

I used a LISP program. (def-auto p(n ct) (if (= n 52) (if (= (mod ct 13) 0) 1 0) (/ (+ (p (+ n 1) ct) (p (+ n 1) (+ ct (mod n 13)))) 2)))
(p 0 0)

[lostdummy]

[ralphmerridew]

IIRC, the exact answer to part 1 is something like floor(n!/e)/n! but I don't remember if that's player 1's or 2's probability of winning, or if it should be floor or ceiling.

[lostdummy]

That is very similar to solution that I found there, being:

p=1 − 1/1! + 1/2! − 1/3! + 1/4! − ... − 1/51! + 1/52!

which is p~ 1/e +- 1/53! , and that i similar to yours which is p~ 1/e +- 1/52!
both end up as p=0.368.


What I have as my simpler solution is:

p= (51/52)^52 , or more generally p=((n-1)/n)^n
Numerically it is p=0.364 , and that is small difference to above (~ 1%)

Reasoning behind my solution, if we have n cards:
-chance for two cards to be same p1= 1/n
-chance for not match is p2=1-p1 = (n-1)/n
-chance not to have match n times is p=p2^n
=therefore p=((n-1)/n)^n


Interestingly, my solution also have same limes, only slower approaching.

[L'lanmal]

The reason the second method is not correct is that each comparison is NOT independant with the rest.

If you only had 2 cards in your decks, there is a 1/2 chance that the top card would be the same. There would be a 1/2 chance the bottom cards will be the same. But the odds of any pair matching is not 1/2 + 1/2*1/2 = 3/4s. Instead, there is a 1/2 chance BOTH match, and 1/2 chance that neither match.

[Trojan Horse]

Yep, L'lanmal has it right. (Oh, and ralphmerridew: I think it should be "rounded off to the nearest unit", not "floor" or "ceiling".)

[lostdummy]

That is correct - while my solution approaches first one for any reasonable high N, it is clearly different for lower number of cards.

On a side note, I wonder if there is any easy way to get to first result ;p

[ralphmerridew]

To get the first result, divide the formula proven on http://en.wikipedia.org/wiki/Derangements by n!.

[L'lanmal]

The probability of any given card matching is 1/n. (There are n cards in the other deck, one of which matches.) There are n cards in the deck. Therefore, there is a probability of n*1/n = 1 that you have a match somewhere.

But wait! You are double counting the times when 2 cards match. The probability any given 2 cards match is 1/n * 1/(n-1). The number of pairs of cards is (n choose 2), which is (n*(n-1))/2. So the odds of this happening is 1/(n*(n-1))* (n*(n-1))/2 = 1/2. Therefore, there is only a probability of 1-1/2 = 1/2 that you have a match somewhere.

But wait! You are overcounting the times when 3 cards match.
. . . Odds: 1/n *1/(n-1) * 1/(n-2). Ways it can happen:(n choose 3).
. . . 1 - 1/2 + 1/6
. . .
. . .
1 - 1/2 + 1/6 - 1/24 . . .

Compare this with the Taylor expansion calculation of e^x around x = -1 (or e^-x around x = 1).

(This process is called "Inclusion/Exclusion".)