»  Solutions to puzzles in my National Review Online Diary

  August 2010

—————————

In my August diary I posed the following brain-teaser.

I have an ordinary deck of 52 playing cards. I shuffle it thoroughly. What is the probability that not one card is in its original position?

Related, but more general:

I have a deck of n cards, numbered from 1 to n. I shuffle the deck thoroughly. Then I turn the cards over one by one. If the k-th card I turn over bears the number k, call that a "match."

What is the probability that after going through the whole deck I shall have tallied m matches, where m is some number in the range from zero to n?

—————————

Solution

The answer to the first question is, to a very good approximation, 1/e, where e is of course the standard mathematical constant 2.718281828459…  (The first million decimal places of e are here.)  1/e is 0.367879441171…, so you're looking at a 37 percent chance, near enough.

The answer is pretty much the same for any large number of cards; the approximation just gets better as the number of cards increases. In fact it's pretty good even for small numbers. For 2, 3, 4, 5, 6, 7, 8, 9, 10 cards the probabilities are, to the same twelve decimal places,

 2    0.500000000000
 3    0.333333333333
 4    0.375000000000
 5    0.366666666667
 6    0.368055555556
 7    0.367857142857
 8    0.367881944444
 9    0.367879188713
10    0.367879464286

 … so that with just ten cards the probability differs from 1/e only in the eighth decimal place.

For the answer to the second, add up the first (n − m + 1) terms of this series

1/0! − 1/1! + 1/2! − 1/3! + 1/4! − …

 … then divide the result by m!  (The exclamation point here of course indicates the factorial function:  5! = 1×2×3×4×5 = 120, for example. By convention, 0! = 1.)

So with four cards, the chance of only one match is (1/0! − 1/1! + 1/2! − 1/3!) divided by 1!, which works out to 1/3.

Note that if (n − m + 1) = 2, your answer is bound to be zero, because 1/0! − 1/1! is zero. That is the mathematical expression of the fact that it's not possible for all the cards except one to be matches!

How do I know any of that? It's a topic in math, with the irresistible name derangement.