If you imagine the scenario that you are in an office with lots of people who you quite like, but not enough to spend time and money on getting them an individual gift, a Secret Santa is the perfect way around that. Because what you do, everybody puts their names into a hat, 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, about Secret Santa, is 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, bath bubbles! Hooray! Or, like, I don't know, a book on numbers. Brady: "What about?! You churn out books on numbers!" I know. I know that's true. 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. They replace it back in the bowl. 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." Exactly. 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 can pick is totally fine. They're either going to pick A or C. And each of those has probability of a half. However, if A has picked B and B has picked A, 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, put your names back in the hat, and then 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, but you can work out the probabilities of each of these happening, if you kind of travel down these arms of the tree. This permutation here of C-A-B which we have up here, this one here, this one is gonna happen with the probability of a half, because it's a half times 1 times 1. This one here, this, this other successful arm of 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. Which might help you when you try and decide where to sit around the table, because, yeah, you don't want, like, some person who's rubbish at presents to be buying for you. So the exact probabilities change depending on how many people you have, but the, the overall idea is the same. That the probability of you buying for a person later on if you go first is different to the probability of you buying for somebody earlier on the tree. Um, so overall, I mean, I think this version of Secret Santa is pretty rubbish, really. It's got two massive problems with it. So what you could do if you wanted, you wait until everyone's got a name, everyone's picked a name out of the hat, and that's when you look at it, and that's when you decide if, if somebody's got their own name. You call a failure, and you start all over again. Unfortunately that one's got a 37 percent chance of failing, and a 5 percent chance of failing more than three times in a row, by which time I think people are gonna be less keen to buy each other presents, and maybe just want to call it a day. However, we've got a solution. We've got a Secret Santa system that does actually work. Okay, what you do now if you want the perfect Secret Santa setup, you create a series of cards. The cards are kind of split in two. And at the top of the card, you write: you are number 4, and on the bottom of card, you write: you are buying for number 4. So whatever the number is on top, the same number is on bottom. So you do lots of cards, you do one for each person. So if you've got 20 people, you write 20 cards. If you've got, whatever, three people, you write three cards. You get all of these cards, you lay them on a table, shuffle them all around, so you have no idea what order they're in, and then, when you're happy that they're neatly shuffled, you go along with a pair of scissors and cut the cards in two. So now you have no idea what cards are next to each other, and you're kind of cutting along the line. And these scissors that everyone draws in school? How do they do them? Like that? They go? That's my scissors. It's not great. You go along and you cut them all up. Now at that point, you can create your derangement. And you can do that just by shifting the top half of all of the cards along by one. By doing that, you're guaranteeing that the number on the top of the card isn't gonna match the number on the bottom of the card. So you've definitely got a derangement, definitely got a Secret Santa system that works. But, also, because you shuffled them, you have no idea what numbers are matching with what numbers. So the next step, everybody who's playing Secret Santa comes along, picks up a new whole card, so top and bottom half that are now matched up together. Say you pick one up and it says you are number 3 and you're buying for number 27. Then the final thing that happens is that you write a list of all of the numbers, put it on the wall of the office or whatever, everyone then comes along, they know what number they are, because the card that they picked up would have told them, and then they come along and then they write their name. Everyone now knows their own number, they know the person they're buying for, but they have no idea who else is buying for anyone else in the Secret Santa system, and everyone has an equal chance of buying for everybody else. I mean there is a final way that you could do this, it's a bit simpler, which is just to go online and use one of the free apps. But, this is much nicer. Brady: "It's fun, you gotta, there gotta be hats and tickets and pulling cards and things." Yeah, I agree. Let's do the traditional way, non-computer way. Brady: "Let me ask you this, mathematician Hannah. Have you ever done this?" Nope. I'm famously stingy when it comes to buying Christmas presents. I won't get involved. If you're in the market for some gifts, and Hannah hasn't put you off the idea of a mathematics book, these are books that she's written. You could try them out. I'll put links in the description along with links to some Numberphile merchandise you could try, like t-shirts and posters. And if you want to see more of Hannah besides here on Numberphile, why not check out her recent guest appearance on Objectivity? Links for that as well.
The animation in this episode is brilliant
Really nice episode! Not sure if it happens in other countries, and is more related to Game Theory maybe, but there is an alternative rules here that people use sometimes. Basically, you buy a normal gift, people pick numbers to decide the order, first one picks a present, opens it. Second person picks a present, opens it, and then he can choose to keep it, or swap with a already unwrapped present. At the end the first person get a chance to swap his present so is fair. This means that picking and keeping a really good present is not the best move, because someone will later "steal it". Sometimes people will have rules so a item can only change hands 2 or 3 times, adding more strategy to the game.
The sort-of easter egg at 0:43... Is that for you and /u/MindOfMetalAndWheels? ;)
Very interesting to think about.
In the original scenario you could just draw your own name and buy yourself a gift -- not to undermine the point of the video though.
love hannah fry! shes brilliant!
I could've sworn there was already a numberphile video about this a few years ago with James Grime, but I can't find it now.
Edit: I was incorrect, it was a singingbanana video.
Brady, what's with the weird glitchy thing at around 1:44? Is that a video equivalent of a watermark?
There's still one problem with anonymity in this solution. You know that the one that you are buying for isn't buying you your present.
fantastic video, incredible animation, love all the jokes and references buried in it. Klein bottle, hello internet LP, I watched it like five times to try and catch everything :)