## Secret Santa puzzle

This problem was inspired by a recent /r/dailyprogrammer exercise on Reddit.  It’s admittedly a little late for a holiday-themed puzzle, but then so was the exercise:

You and your large extended family participate in a Secret Santa gift exchange, where everyone is randomly– and secretly– assigned another person for whom to buy a gift.  To determine the gift assignments, everyone writes their name on a slip of paper and puts the slip into a hat.  Then each person in turn draws a slip from the hat, buying a gift for the person whose name is on the slip.

One obvious requirement is that no one should draw their own name.  However, there is an additional restriction: no one should be assigned to buy a gift for anyone in their immediate family: husbands cannot buy for their wives, parents cannot buy for their children, etc.  Roughly, you cannot buy for anyone that came in the same car with you.

Instead of drawing slips from a hat, the /r/dailyprogrammer exercise involved writing a program to generate the gift assignments for a group of 30 people comprised of immediate family sizes of {1, 1, 2, 1, 2, 4, 3, 1, 1, 2, 1, 2, 1, 1, 3, 2, 2}.  I saw several different approaches in the submitted solutions: some programs were actually deterministic, forgetting that the assignments should be random.  Other programs constructed an assignment iteratively or recursively, essentially modeling the sequential draw-from-a-hat method… but sometimes getting “stuck” near the end in situations discussed here before, where all remaining unassigned persons are in the same family.  (And even when these programs don’t get stuck, not all of the resulting assignments are equally likely.)

Finally, what I thought were the cleanest solutions used rejection sampling to eliminate these problems: keep generating random unrestricted permutations until finding one that satisfies all of the intra-family buying restrictions.

Problem: Your family does the same thing: if at any point in the drawing process, anyone draws their own name or the name of anyone in their immediate family, everyone puts their slips back into the hat, and the process is re-started from the beginning.  On average, how long will this take?  That is, what is the expected number of times the drawing process must be started before it successfully completes?

This entry was posted in Uncategorized. Bookmark the permalink.

### 1 Response to Secret Santa puzzle

This site uses Akismet to reduce spam. Learn how your comment data is processed.