Name: The Problems with Secret Santa - Numberphile
Uploaded: 2020-03-27T18:13:15.000Z
Duration: 11 min
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

If you imagine the scenario that you are in an office with lots of people who you quite like, but not enough

To-infinitive

to spend time and money on getting them an individual gift, a Secret Santa is the perfect way around that. Because what you do,

everyone picks a single name out of a hat, and you buy one crappy present

for just one person in the office, then everyone gets to walk away with a crappy present. The important thing, though,

kind of clue's in the name. It is supposed to be secret. Nobody is supposed to know who bought

anybody else's present, apart from the one that you buy. Everything is completely anonymous. That's sort of a

fundamental rule of, of the Secret Santa agreement.

I guess it's so you can get away with buying basically junk for other people.

I mean they're always crummy, they're always crummy, aren't they? Because people don't really know you. So it's always like,

Or, like, I don't know, a book on numbers.

Brady: "What about?! You churn out books on numbers!"

But, yeah, like an encyclopedia of numbers, you know?

Brady: "Right, because you're the math person."

Yeah, exactly, exactly. Or like, you know, there's a,

there's a guy who's a geographer here, and every single time he always gets something with a map on it.

Just a generic bland map. Because obviously he must love maps.

I think there are two fundamental things that you need for a perfect secret Secret Santa: 1) total anonymity,

and 2) everyone should have an equal probability of being selected by anybody else, right?

Those are kind of two fundamental things. Now the normal way that you do this,

of everybody writing their name down putting in a big bowl and picking a name of a hat, fails on both of those fronts.

Okay, so imagine you've got everybody who's involved in your Secret Santa sitting around a table.

Everybody writes their own name onto a piece of paper and drops it into a bowl in the middle.

And then that bowl is passed around the table and people pick out names of who they're gonna buy the gift for.

If they pull out their own name, though, they read it and replace it back in the bowl, and then pick another name.

By doing that, you have to sort of consider the situation where the last person around the table picks out their own name.

Now if they do that, what, how do you solve it without violating the rule of anonymity?

Because they can't swap it with anyone else,

because by doing so, they would know exactly who is buying them a present.

So, the only real fair thing to do in that situation

is to scrap whole thing, start all over again. There's quite a good chance of that happening.

So, if you have twenty people sitting around your table,

there's a 4% chance that the last person will pull their own name,

and you have to scrap it, and completely start all over again. If the second to last person pulls their name, if the third to last person

pulls their name, you know, all sorts of anonymity issues can be violated.

The chance of anybody pulling anybody else's name is not uniform.

It depends on where you're sitting around that table. Because what you're looking for in this scenario,

you are looking for something called a derangement.

So it's a type of permutation where nobody ends up with their own name, effectively.

Okay, so imagine you've just got three people playing. You've got A, B and C. Now even though there are six ways

that this can be reordered, there are only two extra permutations here that could work for Secret Santa.

Two derangements, they're called. So there are other permutations, of course.

But the problem is, is that any of these three, in every case, somebody, if they're sitting around table in A, B and C,

somebody will end up with their own name. So this column here is kind of who that person is pulling out.

So if A is the first person on the table, they're going to pick their own name in this permutation,

B will pick their own name in this permutation, and C will pick their own name in that permutation.

So none of those are allowed. None of those are allowable Secret Santas.

The question is, how likely is it that each of the people end up

buying for a particular person? And it turns out that the order that you're sitting around the table

makes a difference to that. A picks first, then B goes second, and C goes third.

So, if we think about the bowl of names for A, we know that if A picks out

their own name, he's going to replace it. Or she.

So really there's only two things that, that A can, can pick out

from that bowl, and then Secret Santa carry on. So that's either B or C. And there's a probability of a half in each case.

Brady: "Because if they pick A it's a non-game."

They read their own name, put it back in the bowl, and then pick again. Okay, so if A ends up picking out B,

now it's B's go. So B's already out of the pile. So there's only two names left, and either one that B

They're either going to pick A or C. And each of those has probability of a half. However, if A has picked B

there's only one name left for C to pick from, which is their own name. And that, my friend, is a fail.

There's a failed Secret Santa. Which means the only fair thing to do, if you want to preserve

everyone's anonymity, is to start all over again from scratch,

start from the beginning. If, instead, B ends up picking C, then we're okay.

There's only one name left in the hat, and that is A's name, and that's absolutely fine.

And that's got a probability of happening of 1. So, that's if A ended up picking B in the first place.

If A ends up picking C, you can still work this through, but there's less going on in this case.

There's only two names left in the hat, it's B and A.

B can't pick themselves. If they did, they'd read it, put it back, which means that

B really only has one name that they can pick out, and the Secret Santa continue, which has to be A.

And that's gonna happen probability of 1.

Which means now, once you get to C, there's only one name in the hat, and it's B's name.

Which also happens with probability of 1.

Okay, so, now you've got these, there's one failure, one absolutely fine derangement that works for Secret Santa, here, and another one here,

probabilities of each of these happening, if you kind of travel down these arms of the tree.

this one is gonna happen with the probability of a half, because it's a half times 1 times 1. This one here, this,

B-C-A, is gonna happen with the probability of

a half times a half, which is a quarter. And then the other branch of this, if you like, is a failure.

So you're also gonna fail with the probability of a quarter.

Which means that A is much more likely to end up buying for C than they are for B.

So even though they're, they're just as likely

to pull out the second person's name as they are the third person's name,

if they pull out the second person's name, half of the time, the whole thing will then fail,

so they'll have to start over from scratch.

So what you end up with in this situation is not only the chance of failure, and having to start it all over again,

but you also end up with a situation which isn't perfectly random.

You don't have an equal chance of buying for other people in the office.

Brady: "So if I'm sitting in a row of three, and I'm the last picker, I know it's most likely that the first picker is buying me a present."

Yeah, it's twice as likely that the first picker's buying you a present than the second picker.