## Snap

Posted by Chris on May 1, 2013 – 10:10 pm

Alice and Bob play the following card game. Each has a shuffled deck of cards. Each takes the top card from their deck. If they match, Alice wins. If they don’t match they take the next card from the top of the deck. They continue like this until either they draw a matching pair, and then Alice wins, or they never get a match and then Bob wins.

What is the probability that Alice wins the game?

May 8th, 2013 at 6:42 am

I think the answer is 1/52+51/(2*52) which is approximately 50.96%.

May 8th, 2013 at 10:09 am

Hi jan. It’s more than that.

May 9th, 2013 at 4:59 am

I guess I was lazy not checking after n=4. Now I have another lazy guess:

1/(1!)-1/(2!)+1/(3!)-1/(4!)+…+1/(51!)-1/(52!) which is approximately 63.21%

May 9th, 2013 at 8:57 am

Hi jan. That’s the exact answer. I’m dying to know how you guessed that.

May 9th, 2013 at 10:51 am

Now I’m wondering why you are dying to know how i guessed. Anyway if you died from not knowing I guess I would be accountable and I couldn’t live with the guilt.

Lets say the deck consists of n cards and that the first deck the cards are number 1 through n. Where one is on top and n is on the bottom. Now lets look at all possible configurations of the second deck.

We want to count all the configurations of the second deck where at least one cards position matches the first deck.

For small n I counted each time in all the configurations where one card would match the card in the first deck. But this counts some configurations multiple times. The configurations where two cards positions matched the first deck are counted double so we have to subtract them. But now we subtracted the configurations where three cards positions matched the first deck double so we have to add them again. Etc. Etc.

By looking at a couple of n the pattern looked credible to me. And then of course I divided by n! in order to get the probability.

Hope I managed to make myself clear. I end up using way more words than I would like to which is the reason I don’t like posting explanations.

May 9th, 2013 at 3:55 pm

Hi jan. Thanks for the explanation. In case you didn’t know, you used what is known as the inclusion-exclusion principle. I believe that this is the most famous example of the use of that principle.

IMO, the answer without an explanation is pretty boring. I’m very happy to see the answer without immediate explanation, because it gives others a chance to have a shot at it.

I’ll tidy up my pre-written explanation and post it soon.

I’m not sure why you’re posts keep on waiting for approval.

May 9th, 2013 at 4:07 pm

It’s all about derangements. Derangements are permutations where none of the permutations have an item in it’s original location. I showed in the hat pick problem that the number of derangements of n (distinct) objects is given by the recursion: d(n) = (n-1)(d(n-1) + d(n-2)) = nint(n!/e), where nint is the nearest integer “function”. For even quite modest values of n, we find that

d(n) ≈ n!/e is a very good approximation.

The relevance is that the probability of none of the cards matching is

d(52)/52!. Just for a laugh,

d(52) =29 672 484 407 795 138 298 279 444 403 649 511 427 278 111 361 911 893 663 894 333 196 201 ≈ 2.967… * 10

^{67}So the probability of Alice winning is

1 – d(n)/n! ≈ 1 – 1/e = 1 – 0.367879… = 0.632120…

You can get a good approximation to the answer using the faulty reasoning that the probability of not matching on a given pair is 51/52 and as you try 52 times you get (51/52)

^{52}= 0.36431…, and 1- that = 0.63568…Another recursion is d(n) = n d(n-1) + (-1)

^{n}and that readily yieldsd(n) = n! (1/1! – 1/2! + 1/3! … (-1)

^{n}/n!)Derangements are also known as subfactorials and then they’re written as !n