Treebeard's Homepage : Stumpers

Treebeard's Stumper Answer
21 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 names
that finish in one exchange loop		 L(3) = 2
p(n) Probability that a legal Secret Santa draw
with 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!

 KidsTotal
Draws		Legal
Draws		Draws with
One-loop		Probability
of Legal Draw		Probability
of One-loop
 nn!d(n)L(n)d(n)/n!L(n)/d(n)
 110000
 22110.51.0000
 36220.33331.0000
 424960.37500.6666
 512044240.36660.5454
 67202651200.36800.4528
 7504018547200.36780.3883
 8403201483350400.36780.3397
 9362880133496403200.36780.3020
 10362880013349613628800.36780.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.

KidsTotal
Draws		Legal
Draws		Draws with
One-loop		Probability
of Legal Draw		Probability
of One-loop
nn!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)  
22110.50001.00000000
36220.33331.00000000
424960.37500.66666667
512044240.36670.54545455
67202651200.36810.45283019
7504018547200.36790.38834951
8403201483350400.36790.33978292
9362880133496403200.36790.30203152
10362880013349613628800.36790.27182817
11399168001468457036288000.36790.24711653
12479001600176214841399168000.36790.22652349
13622702080022907929324790016000.36790.20909860
14871782912003207110104962270208000.36790.19416299
151307674368000481066515734871782912000.36790.18121879
1620922789888000769706425174513076743680000.36790.16989261
17355687428096000130850092279664209227898880000.36790.15989893
18640237370572800023553016610339503556874280960000.36790.15101566
191216451004088320004475073155964510064023737057280000.36790.14306746
2024329020081766400008950146311929020001216451004088320000.36790.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.

KidsLegal Draws
(counted)		Legal Draws
(calculated)
d(n) = [n!/e]		p(one-loop)
(counted)		p(one-loop)
(calculated)
p(n) = e/n
2111.000000001.35914091
3221.000000000.90609394
4990.666666670.67957046
544440.545454550.54365637
62652650.452830190.45304697
7185418540.388349510.38832598
814833148330.339782920.33978523
91334961334960.302031520.30203131
10133496113349610.271828170.27182818
1114684570146845700.247116530.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:

In our case,

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!

Back to Stumper

Last modified .

Copyright © 2002 by Marc Kummel / mkummel@rain.org