Treebeard's Homepage : Stumpers

# Treebeard's Stumper Answer21 December 2001

I should know better, but here's another tough bonus stumper. We had a memorable last day of school before the holidays. We went caroling at the Solvang Lutheran Home; we had our school gift exchange; we all went to see the Fellowship of the Ring movie premiere; and we ended at my house with a relaxed staff party. Busy day, but this interesting stumper came up to bother me!

Secret Santa

At Dunn Middle School, we play "Secret Santa" for the holidays. We write our names on slips of paper and put them in a hat, about 20 kids per class, and each student draws a secret name. On the last day of school before vacation, we present our small gifts and homemade cards. Someone presents their gift to start, then the recipient, and so on until we're done. This year the 6th and 8th grades went through their classes one by one, but the 7th grade gift exchange broke twice when a student was called who had already gone. What is the probability of getting through a chain of 20 names unbroken? What about n names?

 DMS students drawing Secret Santa names and exchanging gifts. If someone draws their own name, they replace it and draw again. (What if the last person draws their own name? It hasn't happened yet!) Each class of about 20 kids exchanged gifts among themselves. Two of our three classes got through the entire gift exchange in one chain of giving and receiving. The third class got through about two-thirds of the kids, but then had to start again after the starting person was called before the end. Then they had to start again for the last two kids who had drawn each other's names. Is this the expected result? What are the probabilities?

I like this stumper. It's a real life math problem, and I can't find a ready analysis in my library or the Web. First I wrote a small BASIC program to find all legal Secret Santa drawings for small numbers of participants and count how many of them finish in a single exchange loop. Then I saw the simple pattern. With n participants, there are exactly (n-1)! single loops out of a total of [n!/e] legal draws, so the probability is (n-1)!/[n!/e], or e/n (for large n). The exact probability for 20 kids is:

 ``` one-loop exchanges 121645100408832000 p(20) = ------------------- = ------------------ = 0.13591409... about 13.6% all legal exchanges 895014631192902000 of all draws. ```

Our school gift exchange was not the most likely result, but we have to expect the unexpected! Keep reading to see how I figured this out.

Notes:

I'm a middle school science teacher, not a mathematician. I'll take my time with this, and borrow when I can.

First, some terminology:

 n! n factorial 4! = 1 x 2 x 3 x 4 = 24 [n] nearest integer [1.8] = 2 and [2.3] = 2 e base of natural logarithms e = 2.718281828...

When n kids put their names in a hat and draw random names, we create a new arrangement or permutation of the original names. Imagine we line up all the kids and count them off with a number rather than a name. Then they draw random numbers from a hat. With just 3 kids in a Secret Santa draw, we can represent each possible draw as a vector like this <3 1 2>, where each person is implied by position. This means:

 which person: 1 2 3 who they draw: <3 1 2>

In this case, person 1 gives to person 3; who gives to person 2; who gives back to person 1, a single loop that satisfies the stumper. Writing <3 1 2> says it all. It's against the rules in a Secret Santa exchange if someone draws their own name/number, so not all possible draws are legal. With 3 kids, it works out like this:

 <1 2 3> not legal, 1 gives to 1 (etc.) <1 3 2> not legal, 1 gives to 1 <2 1 3> not legal, 3 gives to 3 <2 3 1> OK <3 1 2> OK <3 2 1> not legal, 2 gives to 2

In this case with n = 3 kids, there are 3! = 1 x 2 x 3 = 6 possible draws. This can be made general for any number of kids. The first person has n choices, the second has n-1 choices, the third has n-2 choices...and the last takes what he gets. The total number of permutations is {n x (n-1) x (n-2) x ... x 1} = n!. This n! (pronounced "n factorial") comes up in lots of questions about probability and combinations. It gives the total number of arrangements or permutations of n objects when the order matters. You probably have a [n!] button on your calculator.

We can now define some more math functions:

 n! possible draws (permutations) of n names 3! = 1x2x3 = 6 d(n) legal Secret Santa draws with n names,where no one draws their own name,also known as derangements d(3) = 2 L(n) legal Secret Santa draws with n namesthat finish in one exchange loop L(3) = 2 p(n) Probability that a legal Secret Santa drawwith n names finishes in one exchange loop p(3) = L(3)/d(3) = 1.0, a sure thing

The stumper is to figure the ratio p(n) = L(n)/d(n) for n=20 or anything else. With just n = 3 kids in the exchange, d(n) = L(n) = 2. It gets more interesting with n = 4 kids. Most of these permutations are not legal since someone draws their own name/number. In a real Secret Santa gift exchange, they would have to draw again. (It gets complicated if the last person draws their own number!)

 <1 2 3 4> <1 2 4 3> <1 3 2 4> <1 3 4 2> <1 4 2 3> <1 4 3 2> <2 1 3 4> <2 1 4 3> OK, 2 loops <2 3 1 4> <2 3 4 1> OK, 1 loop <2 4 1 3> OK, 1 loop <2 4 3 1>

 <3 1 2 4> <3 1 4 2> OK, 1 loop <3 2 1 4> <3 2 4 1> <3 4 1 2> OK, 2 loops <3 4 2 1> OK, 1 loop <4 1 2 3> OK, 1 loop <4 1 3 2> <4 2 1 3> <4 2 3 1> <4 3 1 2> OK, 1 loop <4 3 2 1> OK, 2 loops

There are now 4! = 1 x 2 x 3 x 4 = 24 possible draws, but only nine of these are legal draws where no one gets their own name, and only six of those complete in one exchange loop. Try a few to see how it works. So for n = 4 kids, 4! = 24, d(4) = 9 and L(4) = 6. The probability of a legal draw is 9 / 24 = 0.375, and the probability that a legal draw is a single-loop gift exchange is 6 / 9 = 0.67.

That's the beginning of a table for n = 3 and 4, and n = 1 and 2 are gimmees. I wrote a BASIC computer program to count the next few values by testing every permutation. Look for patterns!

 Kids TotalDraws LegalDraws Draws withOne-loop Probabilityof Legal Draw Probabilityof One-loop n n! d(n) L(n) d(n)/n! L(n)/d(n) 1 1 0 0 0 0 2 2 1 1 0.5 1.0000 3 6 2 2 0.3333 1.0000 4 24 9 6 0.3750 0.6666 5 120 44 24 0.3666 0.5454 6 720 265 120 0.3680 0.4528 7 5040 1854 720 0.3678 0.3883 8 40320 14833 5040 0.3678 0.3397 9 362880 133496 40320 0.3678 0.3020 10 3628800 1334961 362880 0.3678 0.2718

At this point, I saw patterns and had to think what they mean. To find a probability, you need the number of favorable outcomes divided by the number of total outcomes. It's easy to figure the number of one-loop Secret Santa draws. With 20 kids drawing names, the first kid has 19 legal choices, since he can't draw his own name. The second kid has 18 choices since he can't draw his own name or the first person's name. The third kid has 17 choices, and so on to the last kid who takes what he gets. For 20 kids, that's 19 x 18 x 17 x ... x 1 or 19! For n kids, there are (n-1)! one-loop exchanges.

It's harder to find the total number of legal draws where no one draws their own name/number. But this is an old math problem related to the classic hat-check problem: If n people check their hats and then grab a hat at random, what's the probability that no one gets their own hat back? As with the Secret Santa stumper, this involves counting the arrangements in which no object appears in its original position. Such arrangements are known as derangements.

The number of derangements can't be solved so easily with factorials, but I found an answer on the Web based on the principle of inclusion-exclusion. (I'll take it as a given, but there's a derivation here, and more in the links below.) For n objects, the number of derangements is

```                  1    1    1    1    1    1          (-1)n
d(n) = n! [ 1 - -- + -- - -- + -- - -- + -- + ... + -----  ]
1!   2!   3!   4!   5!   6!          n!
```

The series in brackets is the first n terms of the Taylor / Maclaurin series for e-1, so it follows that d(n) --> n!/e for large n. That's how that ubiquitous number e sneaks into the answer. And in fact the expression [n!/e], where the brackets mean "nearest integer," seems to give exact answers for any n, large or small.

That mysterious number e is a transcendental number like pi and phi (the Golden Mean) and (more than) infinitely many more. It can't be expressed as a fraction or as the root of a simple polynomial equation in the way that the square root of 2 is the solution of x2 - 2 = 0, but it appears as the limit of many series and processes. It's important in problems about compound interest, growth equations, normal distributions, natural logarithms, and much more.

```              x2   x3   x4    x5   x6         xn
ex = 1 + x + -- + -- + -- + -- + -- + ... + -- + ...
2!   3!   4!   5!   6!         n!

e  = 2.718281828459045235360287471352662497757247093699959574966967627724076630353
547594571382178525166427427466391932003059921817413596629043572900334295260
595630738132328627943490763233829880753195251019011573834187930702154089149
934884167509244761460668082264800168477411853742345442437107539077744992069
551702761838606261331384583000752044933826560297606737113200709328709127443
747047230696977209310141692836819025515108657463772111252389784425056953696
770785449969967946864454905987931636889230098793127736178215424999229576351
482208269895193668033182528869398496465105820939239829488793320362509443117
301238197068416140397019837679320683282376464804295311802328782509819455815
301756717361332069811250996181881593041690351598888519345807273866738589...
```

Now we have the final answer for the Secret Santa stumper. The probability of getting through a Secret Santa draw in just one loop is:

```
favorable outcomes   L(n)   (n-1)!   (n-1)! e   e
p(n) = ------------------ = ---- = ------ = -------- = -
total outcomes     d(n)     n!        n!      n
--
e
```

There's also a neat recursive way to figure d(n) from the previous value:

```  d(n) = n d(n-1) + (-1)n
```

That "(-1)n" term just means add 1 if n is even and subtract 1 if n is odd. In fact, all the terms of this stumper can be defined recursively, which makes it easy to generate a table of any size in a spreadsheet like Excel. Note that the probability of a legal draw (or derangement) quickly converges to 1/e or e-1.

 Kids TotalDraws LegalDraws Draws withOne-loop Probabilityof Legal Draw Probabilityof One-loop n n! d(n) L(n) d(n)/n! L(n)/d(n) = n(n-1)! n d(n-1)+(-1)^n (n-1)! = (n-1) L(n-1) 2 2 1 1 0.5000 1.00000000 3 6 2 2 0.3333 1.00000000 4 24 9 6 0.3750 0.66666667 5 120 44 24 0.3667 0.54545455 6 720 265 120 0.3681 0.45283019 7 5040 1854 720 0.3679 0.38834951 8 40320 14833 5040 0.3679 0.33978292 9 362880 133496 40320 0.3679 0.30203152 10 3628800 1334961 362880 0.3679 0.27182817 11 39916800 14684570 3628800 0.3679 0.24711653 12 479001600 176214841 39916800 0.3679 0.22652349 13 6227020800 2290792932 479001600 0.3679 0.20909860 14 87178291200 32071101049 6227020800 0.3679 0.19416299 15 1307674368000 481066515734 87178291200 0.3679 0.18121879 16 20922789888000 7697064251745 1307674368000 0.3679 0.16989261 17 355687428096000 130850092279664 20922789888000 0.3679 0.15989893 18 6402373705728000 2355301661033950 355687428096000 0.3679 0.15101566 19 121645100408832000 44750731559645100 6402373705728000 0.3679 0.14306746 20 2432902008176640000 895014631192902000 121645100408832000 0.3679 0.13591409

The transcendental number e sneaks into this stumper as the limit of an infinite series. But real gift exchanges are not infinite. Here are my program counts of total derangements and the probability of getting through an exchange in one loop. I'm impressed that the number of derangements calculated as [n!/e] is exact. The calculated probability p(n) = e/n matches to 8 decimal places after n = 10.

 Kids Legal Draws(counted) Legal Draws(calculated)d(n) = [n!/e] p(one-loop)(counted) p(one-loop)(calculated)p(n) = e/n 2 1 1 1.00000000 1.35914091 3 2 2 1.00000000 0.90609394 4 9 9 0.66666667 0.67957046 5 44 44 0.54545455 0.54365637 6 265 265 0.45283019 0.45304697 7 1854 1854 0.38834951 0.38832598 8 14833 14833 0.33978292 0.33978523 9 133496 133496 0.30203152 0.30203131 10 1334961 1334961 0.27182817 0.27182818 11 14684570 14684570 0.24711653 0.24711653

I think I got the answer, but that's not the end of this stumper. I did find one paper on the Web that considers a slightly different Secret Santa puzzle on what percent of legal draws do not contain a 2-cycle where two people exchange gifts with each other. The authors call this number T(n). They find that the ratio T(n)/d(n) converges to 1/SQRT(e) or e-1/2 for large n. This makes me wonder whether the ratios of other gift exchange loops of different sizes converge to fixed vales even though the chance of making it through the entire draw in one loop grows smaller and smaller.

Consider a draw with 8 kids. These variations are possible, remembering that a 1-loop is not allowed since no one can give a gift to themself:

 8-loop 6-loop + 2-loop 5-loop + 3-loop 4-loop + 4-loop 4-loop + 2-loop + 2-loop 3-loop + 3-loop + 2-loop 2-loop + 2-loop + 2-loop + 2-loop

These are just the addition partitions of 8, excluding any partition with a 1, since no one can exchange gifts with themself. Partitions have come up in my stumpers before, and I have a BASIC program to figure them. I think the next step is to run every possible derangement for different size groups, and count how they break down in these different loops. I suspect there will be interesting patterns that all involve e. I reckon I'm lucky to find an unexplored math problem that's not over my head, but I haven't had time to take it further. Maybe this summer!

Graybear also explored this interesting stumper, and got some real data:

I decided to try simulation with playing cards. I numbered spaces on the table from 1 to 20 to represent the people, and used the ace through 10 of hearts and spades to represent the slips of paper in the hat. I would then shuffle the cards and then deal them face-up, one-at-a-time onto the numbers. If a card matched the number on which it was placed, it was put back in the stack to represent someone pulling their own name. Once all the cards were dealt, I picked up the card on #1 and sent it to its rightful spot. Then I picked up whatever card was there and sent it to where it belonged, and so on, until I picked up the ace of hearts which ended the game. At that point, I had either moved all 20 cards or not. My results so far are:

 Last person drew own name: 4 Got through all 20 without restarting: 15 Did not get through all 20: 65 Total simulations: 84

I figured that the last person would draw his own name 1/20th of the time, and my simulation indicates that, as well. Of the remaining 80 simulations, only 15 completed the circuit in one shot for an average of 18.75%. I'm hoping you are creating a VBasic program to solve the problem either precisely, or by simulation.

I did write that program Graybear, though I used good ol' DOS Basic. I figure 13.6% is pretty close to your 18.75%

Now we can go back to the original question. When we did the gift exchange at school, the 6th and 8th grades got through the entire gift exchange in loop, but the 7th grade only got through about two-thirds of the kids, and then had to start again after the starting person was called before the end. Then they had to start yet again for the last two kids who had drawn each other's names. Is this the expected result for three draws with twenty kids each? What are the probabilities?

This is an example of a Bernoulli distribution. We have a sequence of independent events such that:

• Each event has two possible outcomes, success and failure
• The probability of success p is exactly the same for each event, and it is not effected by previous outcomes.
• The probability of failure q is given by q = 1 - p.

In our case,

• Success consists of getting through the gift exchange in one loop. We have learned the probability of success with 20 kids is about p = 0.136
• Failure consists of getting through the gift exchange in more than one loop. The probability of failure with 20 kids is q = 1 - p = 0.864
This binary tree diagram shows all possible outcomes. Our Christmas school outcome is shown in red:

The probability of our school result is given by P = p2q = 0.136 x 0.136 x 0.864 = 0.016, or 1.6%. But our result was not quite that remarkable since there are three different ways to get two successes and one failure. There are also three different ways to get two successes and one failure. And there's just one way to succeed or fail in every draw.

Those numbers 1, 3, 3, 1 should look familiar, since they are the 4th row of Pascal's Triangle. Each number is the sum of the two numbers above it. These numbers constantly come up in problems about probability, combinations, binomial coefficients, and binary trees. It's handy they are so easy to calculate.

```                                    1
1   1
1   2   1
This row -->        1   3   3   1
1   4   6   4   1
1   5  10   10  5   1
1   6  15  20   15  6   1
1   7  21  35   35  21  7   1
```
So our final probability table looks like this:

 All three classes finish in one loop (1 way) P = 1 (p3) = 1 x 0.136 x 0.136 x 0.136 = 0.0025 Two classes finish in one loop (3 ways) P = 3 (p2q) = 3 x 0.136 x 0.136 x 0.864 = 0.0479 One class finishes in one loop (3 ways) P = 3 (pq2) = 3 x 0.136 x 0.864 x 0.864 = 0.3046 No class finishes in one loop (1 way) P = 1 (q3) = 1 x 0.864 x 0.864 x 0.864 = 0.6450 Total (8 ways) = 1.0000

I figure we only had about a 5% chance - 1 in 20 - of finishing two of our three Secret Santa draws in a single exchange loop. But there it is.

Chance is always powerful. Let your hook be always cast;
in the pool where you least expect it, there will be a fish.

- Ovid

Here are some links for further research on this stumper. Links help, but the real challenge is to think!

• My best resource on this stumper was a paper by Kelly M. McGuire, George Mackiw, and Christopher H. Morrell from Loyola College, Baltimore, Maryland. They have a paper on The Secret Santa Problem, since published in the Mathematical Gazette, November 1999. The Web link is to a Micro\$oft Word DOC file preprint. Despite the name, the authors consider the different problem of two-person loops. I learned a lot from this paper, thanks.

• The principle of inclusion-exclusion comes up in many problems starting with a gambling game called Jeu de Treize (Thirteen) analyzed by Pierre de Monmort in 1708. Peter Doyle, Charles Grinstead, and J. Laurie Snell describe the game like this:
One person is chosen as dealer and the others are players. Each player puts up a stake. The dealer shuffles the cards and turns them up one at a time calling out, "Ace, two, three,..., king", just as in frustration solitaire. If the dealer goes through the 13 cards without a match he (or she?) pays the players an amount equal to their stake, and the deal passes to someone else. If there is a match the dealer collects the players' stakes; the players put up new stakes, and the dealer continues through the deck, calling out, "Ace, two, three, ...". If the dealer runs out of cards he reshuffles and continues the count where he left off. He continues until there is a run of 13 without a match and then a new dealer is chosen.

The connection is that we're counting arrangements or permutations in which nothing appears in its original position. Some other games and stumpers based on derangements include the hat-check problem, frustration solitaire, menage problem, dinner-table problem (PDF), Latin rectangles, and letters and envelopes.

• There's a good practical discussion of the principle of inclusion-exclusion by Brian Alspach here and here, reprinted from Poker Digest. (Check here for more by the author.) There's a math account at Ask Dr. Math (and here), and another in their problem archive. There's also an Ask Dr. Math e FAQ with lots of links.

• There's a wealth of math info at Eric Weisstein's World of Mathematics site hosted by Wolfram's Mathematica. Start with the pages on permutation, probability, and derangement, and see where you go! I learned that the number of derangements of n objects is also known as the subfactorial of n, and written as !n. Robert Dickau has some interesting visualizations of derangements. There's a real textbook on probability and combinations available from the interesting Chance! site at Dartmouth. A Google search on "derangement" comes up with all kinds of interesting hits about other kinds of derangement!

• You can download my simple SANTA.BAS (37K) program for QBasic/QB/PDS from Treebeard's Basic Vault. It counts Secret Santa draws that finish in one loop, but that's all for now. It will be more interesting if I can count exactly how the other legal derangements fail to finish in one loop. This involves partition theory. There's more info, links, and my PART2K.BAS (50K) BASIC program to count partitions at my Millennium Magic (17 Dec 99) and Holiday Magic (18 Dec 98) stumpers. There's more info on Pascal's Triangle in my stumpers about Tricky Tetrahedra (26 Oct 2001) and The Twelve Days of Christmas (12 Dec 1997).

Back to Stumper