A gift giving puzzle (Secret Santa math)

Happy New Year! I am getting back in the groove of things, so posting might be slow for a couple weeks. In the meantime, another puzzle!

During the holidays, I was part of a couple gift exchanges, and that experience reminded me about a problem that Chris mentioned a while ago in a comment for a previous post. Here is the problem:

N people put their names into a hat, then they all draw a name. The draw is successful if no one draws their own name. How likely is that?

The puzzle was perhaps inspired by Secret Santa, a gift exchange in which everyone draws a name to give a gift to. The assignment is legal if no one draws his own name (gifting to oneself is not much fun). The puzzle is alternately stated as: how likely is it that a Secret Santa draw is a permissible assignment?

Can you figure it out? The answer is below.

Solving small cases

Let’s try to figure out a pattern from analyzing a few small cases.

A bit of notation can help. We can arbitrarily label the people with numbers 1, 2, …, n. Further, we can think about a draw as a permutation of these numbers.

I’ll use the following shorthand (which is standard permutation notation). If there are three people, for example, then the notation 312 means “the first person drew name 3, the second person drew name 1, and the third person drew name 2.”

Let us consider the case of n = 3. The possible number of draws is the number of permutations of three items, or 3! = 6. How many of these draws are permissible–that is no one chooses his own name? We can directly list these out:

231
312

You can verify these are the only two derangements. Thus, we can conclude for n = 3 that the probability is

Probability(3) = 2 / 3! = 2 / 6 = 1/3 = .33333….

From this case we have figured out a solution method. We need to find the number of permissible solutions and divide it by the number of total draws (which will be equal to n!)

So what happens with four people? How different is the probability then?

The total number of draws is 4! = 24. The number of permissible draws can be figured out by direct counting, and we find there are 9 of them:

2143, 2341, 2413,
3142, 3412, 3421,
4123, 4312, 4321

So this time the calculation is:

Probability(4) = 9 / 4! = 9 / 24 = 1/3 = .375

It’s interesting the probability did not change by very much from the case of n = 3.

It would be unwise to proceed in higher and higher cases by direct counting. We already have a formula for the total number of cases in the denominator (n!). What we need is a formula for the number of permissible cases in the numerator.

The general solution

How many ways can a set of objects be rearranged such that no object remains in its initial position?

There is a special name for this kind of permutation. It is known as a derangement. Also, because of its relation to permutations, there is a special notation for derangements. A derangement of n objects is abbreviated as !n with the exclamation point appearing before the symbol.

Counting the number of derangements can be done in a couple of ways, well beyond this blog’s scope, and their detailed proofs are here.

I will mention that the method I prefer uses the inclusion-exclusion principle. The idea is to count the total number of permutations (n!) and then subtract out any permutation that fixes one or more points. The tricky part is to make sure you don’t double count, which is where the inclusion-exclusion formula comes in. The formula specifies how to add and subtract various subsets (like fixing one point, two points, three points, etc) so that the resulting figure does not double count.

Using the inclusion-exclusion formula, the formula for the number of derangements is:

!n = Total permutations – permutations fixing 1 point + permutations fixing 2 points …. +/- permutations fixing n points

The interesting part is the summation term. This is familiar as the partial sum for the Taylor series expansion of 1/e – quite an interesting development!

Thus, the number of derangements is well-approximated by !n = n! / e (the exact formula is !n = floor(n! / e + 1/2) since you need to round up for even numbers and round down for odd numbers).

So we can now solve the puzzle as n approaches infinity. The probability is:

Probability(n) = !n / n! ~ (n! / e) / (n!) = 1/e = 0.3679

It’s again remarkable that e appears in a probability problem, and the answer is roughly 37 percent which is reasonably high.

On a closing note, here is another probability problem where the solution ends up a lot higher than you might initially expect.