How to randomize Secret Santas if participants are far away and without internet

There are 3 weeks left until the New Year, which means it’s time for “Secret Santa”. But what if not all friends or relatives can gather in the same drawing room? You will say that you can use a special application, where all the names are driven in, and then randomly sent to the participants. Right, such applications really lot… But what if the person doesn’t have a smartphone or email? Yes, it’s hard to believe, but such people do exist. It remains to be confused and send out paper letters. But here, too, everything is not so simple, because the rally may not take place.

Just in case, let’s recall the rules of “Secret Santa”. Participants write their names on pieces of paper, put them in a hat, and then each draws out someone’s name. It is this person who needs to buy a gift. Usually the donor remains unknown, although confession is not prohibited.

The algorithm of the game, so that it is definitely clear:

Write the names of friends / relatives / colleagues on pieces of paper;
Put the names in a header;
Each one in turn pulls the name out of the header;
If you pulled out a piece of paper with your name, go back to step 2;
Prepare a gift and give it.

So, a possible problem is that a person can receive a letter with their name. In this case, the entire draw will have to be restarted. That is, write new letters to all participants. And if someone pulls himself out again …

To fix this, you can send out several draws at once and use the one that goes well. But how many draws should there be for everything to be guaranteed to work out at least in one of the cases?

Santa with a 99% guarantee

So how many draws does it take for us to be 99% sure of getting the right pairs? This situation is a special case. binomial distribution that has the following formula for determining the probability of getting exactly r successes out of n attempts with probability p:

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

But what we really want is the likelihood of one or more successes, which is logically the opposite of the likelihood of no success at all. When you plug this into a binomial formula, it simplifies to:

1- (1-p)ⁿ

But what is p?

One way to determine p is to manually write down the set of valid results for different group sizes.

n	Successful	Permutations (n!)	p (approximately)
one	0	one	0
2	one	2	0.5
3	2	6	0.333
4	9	24	0.375

Probability table for success in n trials

It turns out that this number varies depending on the size of the group, but it approaches a value just above 1/3. In our case, I want to know p for a group of 6 people, so computer calculations are needed to find the answer.

In Python, it is possible to write a solution in one line, but for clarity, I’ve broken it down into 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

This creates an iterative Python object that includes all combinations of the array [1, 2, 3, 4, 5, 6]… If we use the order of the numbers in the array to denote a pair (i.e., the first element corresponds to the first Santa, the second element to the second, and so on), then the layout [1, 2, 3, 4, 5, 6] is clearly the worst draw, as each Santa will pull himself out.

Thanks to the itertools module, we can use this abstraction to represent all possible draws of the six Secret Santas as arrays (spoiler alert, this list is as long as 6 !, which is 720).

But how to check if the draw has taken place? The easiest way to find out is to subtract each Santa’s start index from the index in the current layout. If, as a result of the draw, someone pulls himself out, there will be one or more zeros in the array, and then we assign the array a value of zero if the draw is invalid, and a nonzero value if the draw took place.

We now know that there are 265 successful draws for a group of six. This is approximately 0.3681.

So how many draws to hold

So, now we want to know how many draws are needed for at least one successful draw with a 99% probability. We could just use our simplified binomial formula to calculate the probability of success after n tries and then stop when we reach 99%, but that’s too boring.

To crack this nut, we need a ScipPy optimizer. He just needs to change our equation so that the desired answer gives zero when entered into a Python function.

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

Thus, we need about 10 draws so that the error occurs only in one case out of a hundred. But if we send out paper letters, then even 10 draws is too much. And the human factor cannot be ruled out, you can make a common mistake when writing letters with rallies.

An alternative approach

Then I took a slightly different approach, which allows us to do as many draws as we want, but this is relevant when the Sant number is small.

Now we know how to generate all the permutations and how easy it is to find successful draws, as well as how many there are in total (for example, 265). This number is not that large, so in this case it is easier to send all Santas a personalized list of the results of all 265 possible successful draws.

On the day of the draw, someone simply chooses a random number from 1 to 265 and everyone looks at who they got. Of course, in this case, the organizer will know the couples, but this is not such a big problem.

So now, if your friends / family are far away, without cellular communication and the Internet, this will not prevent you from exchanging gifts!

What else is interesting in the Cloud4Y blog

→ IT Pizza Quest. Outcomes

→ How I accidentally blocked 10,000 phones in South America

→ Keyboards that failed

→ Can you smell it? Smells like your data leak

→ Examining our hardware: resetting BIOS passwords on laptops

Subscribe to our Telegram-channel so as not to miss another article. We write no more than twice a week and only on business.