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:
|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!
4 thoughts on “The Secret Santa Problem”
I have talked a lot about this with Jeremy, but I wasn’t at the holiday party, so maybe he was talking about it with someone else at the time?
Anyway, its a nice problem, and I like the treatment you gave it here.
Also, I have a solution to the full problem (that I am pretty sure is not the solution you have in mind), so I will leave it here (I hope that’s okay).
Each person in the office sits in a circle, and closes their eyes. One person is designated the counter. He counts to 100, out loud, repeatedly. Each time he gets to 100, each employee MAY open their eyes. When this happens, everyone who opened their eyes looks around to see if they are the only one with open eyes. For now, lets assume they are.
If the one candidate with open eyes sees that no one else is sitting in the middle of the circle, they go and sit in the middle of the circle. (NOTE: LET’S CALL THE PERSON THIS HAPPENS TO PERSON X.) If they DO see someone sitting in the middle, they go tap that person on the head, then go sit back down.
At the next 50, the person in the middle of the circle (if tapped) goes and sits back in their original spot. At the next 75 the person who tapped the previous person in the middle goes and sits in the middle.
The person who saw someone sitting in the middle and tapped them on the head will now buy a gift for this person. One down.
Now the process continues, each time someone taps someone on the head, they know that they will buy a gift for that person. Then they go sit in the middle, so someone will buy a gift for them. After this person gets tapped and leaves the middle, they won’t open their eyes again until the end of the process. This process continues for a while. Eventually, PERSON X once again opens his/her eyes, and this time finds someone in the middle. They tap them, and sit back down in their spot, only since they have already been in the middle, they don’t go back to the middle at 75.
Now, after a long time (at least enough that the game COULD have ended in success), the counter declares the game over. At this point, the counter asks everyone if they have tapped someone once, and been tapped once. If the answer is yes, then we have successfully created a secret santa list that meets the criteria. If the answer is no, then the game is a failure, and they play again.
One more thing: it is possible that at some point, when the counter hit 100, two or more people will open their eyes at the same time. If this happens, they all close their eyes, and the game continues as if no one opened their eyes at that time step.
So the final question: how do I know that this game will eventually end in success. Well, the probability of success is greater than 0 (because for each time step at which the counter declared the game over, there are only a finite number of possible games that happened at that time step, and you can count which ones would have been successes), so if we play this enough times, it is guaranteed to end in success eventually.
There, long and annoying, but solved :).
It’s Kathy with a K!
Awesome post. The graphs make things REALLY clear.
Comments are closed.