How to do a Secret Santa so that no one gets their own name?

Brecon Beacons national park

Last summer I went on holiday with some friends, and we decided to go to Hay-on-Wye, the famous town of books. We thought it would be fun to do a Secret Santa while we were there - each of us would buy a book secretly for someone else and at the end of the day we would give them to each other. But how to choose who would buy for whom?

If you have thought about this recently, you probably will have started with just drawing names from a hat, but quickly realized the problem: What to do when someone draws their own name?


Well, they could just put it back and draw again. But then they know that everyone who has drawn before them definitely isn't getting them a present - it must be someone drawing after them. Even worse, what if they are the last person to draw? This is particularly likely with a small group, like the five of us in Wales.

You could just call the whole thing to a halt every time someone gets their own name - start all over again with all the names back in the hat, and keeping going until it works. But this might take ages - and more to the point, it's inelegant!

A diagram of the walk we were on
whilst discussing these matters

If we have a computer program to do it for us it's easy, or equally if we have a trustworthy third party who is not in the Secret Santa. But that seemed like cheating. So instead we spent long hours devising algorithms. In the end we came up with two. Each of them is guaranteed to finish in finite time and with no one knowing anything about who anyone else is buying for (with one exception, see below). They require trust in the other participants.

There is a simple one. And a monstrously complex one. In the end we did the monstrously complex one, for fun, but in this blog post I'll just detail the simple one. The simple one leaks one piece of information: You know that the person you are buying a present for isn't buying you a present - they are definitely buying it for someone else in the group. But that's all you know.

The method

Everyone has to be honest for this to work.

Say you have N people. Get N pieces of card and on one side number them from 1 to N. Now, shuffle them face down, and deal them out at random. Everyone now has one card with a number on it. Everyone should memorize their number. Without showing anyone the number, they should turn the card over and write their name on the other side.

(Various people have also suggested that if you are in a large group who do not all know each other well, you could also write a few facts about yourself, preferences and so on.)

Leaving the name side up, stack all the cards in a pile in the centre. Shuffle them thoroughly without anyone looking (including the person doing it). Then flip the deck over so the numbers are face up. (If you look while you are shuffling you will end up knowing, for example, which name is on top and so which name will be last when dealing out).

Deal the cards number-side up in a row, from left to right so that everyone can see them. Make sure everyone knows which way "up" is - which is the left end and the right end. Like this:

Now everyone needs to leave the room (or turn their backs) and one at a time each person enters to find out who they are getting a gift for. It doesn't matter what order people go in (it definitely shouldn't be the order of the numbers, because that would give the game away - go alphabetical if you really need an order). When you come into the room, find your number. Then pick up the card to the right of your card and look at the name on the back. That is who you will be buying a present for. Put the card back the way you found it. 

If your number is the last card (the one on the right hand end of the row) then you should look at the first card (the one of the left hand end of the row). If you prefer, you could deal the cards out in a clock shape, instead of a row, to make this simpler for people to understand.

Once everyone has gone in you are finished. Carefully gather up the cards and dispose of them in some way so that no one sees them.

A quick summary

1. Number cards from 1 to the number of people
2. Shuffle and deal them out face down
3. Everyone memorises their number and writes their name on the other side of the card
4. Return the cards name up and shuffle them again.
5. Flip the deck over and deal the cards out in a row, number-side up
6. One by one in secret, look at the name on the card to the right of the one with your number on and put it back. If you card is on the right hand end of the row, look at the card on the left hand end of the row.
7. Dispose of all the cards without looking at them further.

Conclusion

What do you think? Can you see any flaws that we missed? As far as I know, the only piece of information that is leaked is that you know your recipient is getting a gift for someone other than yourself.

This method always gives a very simple single cycle graph. (A -> B -> C -> A). But I don't think that is a problem. However, if you want to make sure that you can have sub-cycles, and if you want the possibility of your recipient being the one getting you a present... well, maybe I'll post up the extremely complicated method some time.

Card background texture from Subtle Patterns.