The Low Tech Secret Santa

We’re all Santas now

Secret Santa, if you didn’t know, is a gift-giving game that seeks to reduce the overall burden of buying gifts to a single gift for one person instead of a gift for every person. It also, usually, place limits on the spend which prevents people over or under buying.

For most people the solution to running a ‘Secret Santa’ is pretty simple but it’s worth repeating the process for clarity:

1. Write the names of your friends/family/colleagues on scraps of paper;
2. Fold the names of the Santas up and put them in your (hacking!) hat;
3. Each Santa takes it in turn to pull out a name from the hat;
4. If any Santa gets themself as their match return to step 2;
5. Buy gifts and exchange them sometime later.

The ‘secret’ part refers to the fact that no-one should know, who is their Santa or any other pairing. It usually also means that you never find out who bought you your gift, but that part is optional and there is often plenty of fun to be had discussing it afterwards.

Trouble at the North Pole

Problems start to arise when you can’t get all of the people who want to participate in the draw in the same physical room at the same time.

Your first thought might be (like mine was) “well surely there’s an app for that where you tap in all the names and the app privately sends out the matches”.

And you’d be right, there are plenty. But what if the person who is remote to the draw doesn’t have a usable mobile device or use email? I know this is hard to believe but these people do exist. And believe me, I have tried to fix this problem by fixing the bigger problem but progress has been slow. So, for now at least, apps and email are out.

Your second thought might be (like mine also was) “I could just use snail mail to send out the draw to the remote persons”. But the problem with this is that there is a chance, if one person or more is remote then one or more of those remote persons get themselves in that draw. This would reset the draw and mean we’d need to do it over.

So obviously I can fix that by sending out multiple draws and selecting the first one that works. Right? So the question then becomes how many trial draws do I need to be certain of a valid gift giving extravaganza?

99% Confident Santas

So how many draws do we need, for us to be 99% certain that those pre-draws will be successful and give us valid pairings? This problem description is a special case of the Binomal distribution which has the following general formula to find the probability of getting exactly r successes from n trials with probability p:

nCr . p^{r}.(1-p)^{n-r}

But what we actually want is the probability of 1 or more successes, which is the logical opposite statement of the probability of no successes at all. When you substitute that into the Binomial formula it simplifies to:

1-(1-p)^n

But what is p?

One way to estimate it is if you write out by hand the set of valid outcomes for different sizes of groups we can get an idea of what sort of values p takes.

It turns out that this number oscillates as the group size increases but it looks like it’s converging to somewhere just above 1/3. In my case I really want to know p for a group size of 6 so a computer is needed to brute force that answer. This is of course in the absence of a specific insight on the nature of the ‘Santa sequence’ which would allow me to calculate the valid outcomes without brute force, but more on that in Part 2.

Turns out that in Python you can write an expression to do that in a one-liner but for clarity I’ve split it onto 3 lines.

>> import itertools, numpy, math
>> santa = numpy.array([1,2,3,4,5,6])
>> sum([1 for z in itertools.permutations(santa) if math.prod(z-santa) != 0])
265

What this does is to produce a Python iterable object which has all the different permutations of this array [1, 2, 3, 4, 5, 6]. If we use the order of the array to indicate the pairing (i.e. the first item corresponds to the first santa, the second item to the second and so on) then [1, 2, 3, 4, 5, 6] is clearly the worst draw since every Santa is paired with themselves.

By using itertools permutations then, we can use this abstraction to represent all possible draws of six Secret Santas as a list of arrays (spoiler the length of this list is the same as 6! which is 720).

But how do we check for a valid draw? One cheap way to know if a draw is valid is to subtract the index of each Santa from the index in the permutation given. If the draw is invalid the subtraction will put one or more zeros in the array, and when you find the product of that array it will be zero if it is invalid and non-zero if it is valid.

Doing this gives the new information we need, that there are 265 valid draws with a group of six people. Which is a p of about 0.3681.

Solved it! Now We Have Two Fails.

So now we want to know how many draws are needed to be 99% confident that one of the draws will succeed. We could simply use our simplified Binomial ‘at least one success’ formula to calculate the probability of success after n trials and then stop when we hit 99% but where is the fun in that?

The ScipPy optimiser is the sledge-hammer we need for this nut, it just needs us to rearrange our equation so that the answer we’re looking for would give zero when put into a Python function.

>> from scipy.optimize import fsolve
>> fsolve(lambda x: 1-(1-265/720.)**x-0.99, 1)
array([10.03406063])

So we need about 10 draws to be confident that it will only go wrong one time in a 100. But, when you think about the mechanics of putting together 10 independent Santa draws and stuffing them in the Royal Mail that feels like a lot of work.

Not only that, there is a much bigger chance that I will mess something up when putting the draws together and it results in a failed draw for a purely human reason (as opposed to a mathematical one).

Another Approach

Then I hit on a slightly different approach which is just a step further towards a generalised approach that could allow us to do as many draws as we want, but probably only when the number of Santas is low.

I now know how to generate all the permutations, and how to identify valid drawings easily, and also how many valid drawings there are (i.e. 265). This number is small enough that perhaps the easiest thing to do, in this case, is to send all Santas a personalised list that gives them their pairing in one of the 265 possible valid outcomes. Then all I need to do is to send out those personalised lists via post and email to all the Santas.

On the date of the draw then someone simply selects a random number from 1-265 and everyone reads their Santa off the list. Sure, as the organiser, I could find out who has which pairing but that’s not really a concern because I really don’t want to know. So I just won’t look.

Conclusion

I ran this process as a trial (to make sure everyone ‘got it’) and then we did it for real on 31st October 2021. I think it worked fine, but we might not really know until the gifts are given. Lol.

This puzzle raised a lot of other questions that I haven’t delved into in this post. In the next post I’ll provide a link to the code that generated the draw sheets that I sent out to my fellow Santas (in-case someone wants to use what I’ve done to run their own Secret Santa) but I’ll also delve into the sequence for p to see if we can answer questions like:

• What does p converge to?
• What if the number of Santas is bigger than 10?

But until then I’ve got some shopping to do. 🙂