Secret santa problem

Solution 1:

If each of you just draws a random name out of the hat, the probability that nobody gets their own or their partner's name is

$$\frac{4752}{40320} = \frac{33}{280} \approx 11.8\%.$$

Thus, the expected number of times you'll need to repeat the process before getting "a solution that works" is $280/33 \approx 8.5$. This could get a bit tedious, but it'll hardly take "all year", at least unless you're both really slow and really unlucky with the draw.

Ps. I went and calculated the odds for other numbers of couples too:

• $2$ couples: $\frac{4}{24} = \frac{1}{6} \approx 16.7\%$ chance of nobody getting their own or their partner's name
• $3$ couples: $\frac{80}{720} = \frac{1}{9} \approx 11.1\%$
• $4$ couples: $\frac{4752}{40320} = \frac{33}{280} \approx 11.8\%$
• $5$ couples: $\frac{440192}{3628800} = \frac{3439}{28350} \approx 12.1\%$
• $6$ couples: $\frac{59245120}{479001600} = \frac{16831}{136080} \approx 12.4\%$

If I'm not mistaken, as the number of couples involved tends to infinity, the probability of nobody getting their or their partner's name should tend towards the limit $e^{-2} \approx 13.5\%$, and thus the expected number of retries needed should tend towards $e^2 \approx 7.4$.

Solution 2:

1) You could have a third party party handle the distribution of cards in the hat so that every draw will be valid.

And after each draw the third party will remove invalid cards and put valid ones for the next draw. That should happen without any of the participants knowledge of how much cards are placed and removed.

The downside is that you will have that person know (or at least have enough information to deduce it) about who draws who.

2) Another solution would be if you take 8 cards with each persons name on one side and then every pair makes a unique mark on the other side and puts them in envelopes.

Then you shuffle the envelops, put the cards on the table unique mark up and everyone draws in sequence. In this way you could distinguish the invalid choice without knowing who's who.

3) A modification of the above idea. Use cards with names, then every couple puts the in unique marked box (or envelopes) and then in a bigger box identical to the other ones.

Then someone puts the boxes in one of the offices, opens the big boxes and choses one card from one of the small boxes. Then everyone goes in one by one.

If no one looks at his own box no one knows if he/she was drawn or not.

UPDATE There is a chance that this scheme will fail if the last pair have less then 2 valid choices.

UPDATE If you have people enter the room randomly and without knowing the order of entrance that will solve the problem. That could be done (without third party) if you have one of the participants pick people at random to go there and then taking the last one.

This I hope works just as needed. :)

On a side Note : I would go for the script - it's easier, but organizing all of the above might be a lot of fun to all.

UPDATE Well the stared look of someone looking at you will be the hint no algorithm can deal with.

Solution 3:

See this algorithm here: http://weaving-stories.blogspot.co.uk/2013/08/how-to-do-secret-santa-so-that-no-one.html. It's a little too long to include in a Stack Exchange answer.

Essentially, we fix the topology to be a simple cycle, and then once we have a random order of participants we can also determine who to get a gift for.

Solution 4:

Edit: I just realized this method does not produce all possible derangements. Each pairing is random, but not as independent as it could be, because this method forces the derangement to be a single cycle.

Dr. Hannah Fry describes in her Book "The Indisputable Existence of Santa Claus" the following method:

You make as many cards as there are people. Each card has the same number twice written on it and each card has a different number. You then turn the cards around, shuffle and arrange them in a line. Then you cut them in half so that you now have two lines of cards with equal numbers each facing each other. Then, still hidden, you shift one of the lines by one. Each person can now pick one pair of cards each from one of the lines. The card from the first line tells them which number they are and the card from the second line tells them whom they are supposed to give a gift to. The only thing that remains is to tell everyone what number they are, best by filling in a list with a mapping from number to name.

For example:

1.

|1| |2| |3| |4| |5| |6|
|1| |2| |3| |4| |5| |6|

2.

|3| |6| |4| |2| |5| |1|
|3| |6| |4| |2| |5| |1|

3.
|3| |6| |4| |2| |5| |1|
|1| |3| |6| |4| |2| |5|
 
```