The Secret Santa Problem

Happy holidays everyone! As Christmas approaches so do the Christmas related problems. I’m not talking about the long lines at stores or the busy days filled with errands, I’m talking about Christmas math problems. Here is one I learned at my department holiday party from Eric Hart and Jeremy Voltz.

This whole post is going to be directed at a general audience.

Secret Santa Problem (simplified). An office needs to determine how to set up a secret santa gift exchange, but they have lost all of their dice and paper! How can each person in the office have exactly one person for whom they are buying a gift and also each person does not know who is buying them a gift?

Here we allow some of the employees to have private conversations if they wish.

Attempt 1: The obvious first thing to do (that doesn’t work) is to have one person tell everyone whose gift they are buying. You can tell right away why this won’t work: It is too much work for that one person the designator will have to designate someone to buy a gift for the designator!

Attempt 1.a: Have the boss tell everyone what they should do. Well… I don’t think the boss is going to like this idea. We should really try to find an internal solution. That is, let’s try to find a solution that does not use anything external (like random number generators, extra people, secret santa consultants, etc.)

What else obviously doesn’t work?

Attempt 2: Everyone could just pick another employee privately. This won’t work because Larry from accounting might get 100 gifts. There is no way to guarantee that this method will ensure that no employee gets more than one gift.

Attempt 3: Have everyone sit in a circle and buy a gift for the person to the left of them. Think about why this doesn’t work. This attempt is very similar to one of the previous solutions (which one?).

In general, finding a bunch of methods that don’t work is a good way to start tackling a problem.

“How often have I said to you that when you have eliminated the impossible, whatever remains, however improbable, must be the truth?” -Sherlock Holmes

Hopefully, if we can find the different extremes of wrong methods we can guess at a middle ground (or “interpolate”).  If the extremes are sufficiently different (or “orthogonal”) then we would like to blend these methods together to get a correct solution. This is all very vague, but the more problem solving you do the more helpful this strategy becomes.

Let us look at the pros and cons of the attempts we have made:

Attempt #	Pros	Cons
1	Easy to describe, only one “mistake”, lots of secrecy	Asymmetric
1.a	Easy to describe, completely secret	Asymmetric, external solution
2	Easy to describe, symmetric, lots of secrecy	Many mistakes possible
3	Easy to describe, symmetric	Too much communal knowledge

What do we notice here? All of these attempts are easy to describe and it seems like we are balancing “secrecy” and “symmetry”. It looks like we have come up with some attempts that hit the extremes of high/low secrecy and high/low symmetry. Maybe we can blend these attempts to get something that is mostly secret and mostly symmetric.

Here is your hint: What if instead of employees we have couples of employees? (Think about this a bit before reading on. I’ll wait.)

…

Any ideas? Well, simplifying a bit let’s look at some small numbers. The problem clearly doesn’t make sense with only one or two people. It also doesn’t work for three people. (Can you see how there just aren’t enough options?) So, let’s try this with four people. Using the hint, let’s say the four people are me, my wife Janet, Sam Coskey and his wife Kathy.

What is the “natural” way of setting up this secret santa?

Attempt 4: Well Janet and I will buy gifts for Sam and Kathy, but we will not tell them for whom specifically we are buying our individual gifts. Sam and Kathy will do a similar thing but buying gifts for me and Janet. Here I know that Sam or Kathy is buying me a gift, but I don’t know for sure which person it is. In this method we have sacrificed a bit of the secrecy (I know that Janet is not buying my gift) and retained a type of symmetry from attempt 2.

For interest’s sake, here are the pictures that I thought of to go with the different attempts. (Please excuse the quality):

The next question is the full secret Santa Problem:

Secret Santa Problem. An office needs to determine how to set up a secret santa gift exchange, but they have lost all of their dice and paper! How can each person in the office have exactly one person for whom they are buying a gift and also each person does not know who is buying them a gift? Moreover, any given person has no information about who could be their secret santa.

I’m not going to attempt this one, instead I’m going to end with a similar question that Sam Coskey gave me over supper:

Sam’s 2-person “secret santa”. Is it possible for two people to each choose a natural number so that both numbers are exactly 1 apart and neither person knows who has the larger of the two numbers?

And a cute generalization:

Father/Son “secret santa”. Is it possible for two players to each choose a human being so that the two humans are father and son, but neither player knows who has the father and who has the son?

I will tackle these problems next week. Until then, happy holidays!