The unbelievable solution to the 100 prisoner puzzle

Today I'm at the Royal Institution to have a look at a math puzzle. Some math puzzles are great because of the joy of working it out for yourself, and others are great because the solution is so counterintuitive it's unbelievable. And this is one of those. So to help me explain it, I'm joined by Alex Bellos, author of many, many math books, and the Guardian Puzzle columnist. Yes, and turn up Mondays for the Guardian Puzzle. There you are. There'll be many more plugs in this video. So what kind of puzzle are we dealing with today? It's a prisoner puzzle. It's set in the maths prison. Right, this is like one of the many, many puzzles where there's a number of prisoners. Correct. And some warden has decided... Yeah, prisons are fantastic places for puzzles. A lot of these puzzles come from information science, where it's all about holding to information, and it can only go from one person to another. And it's very believable if you were to say, OK, I'm this kind of evil, sadistic maths warden of this prison. You are going to only be able to do this. You are going to be able to do that. You're not going to be able to talk, anything. OK, I get it. Yeah, it makes sense they're locked in a room, and then they're one by one in this room. If you were setting it in like a school playground, you'd think it's a bit more... You'd be like, this is questionable. I first came across this version of the puzzle in Alex's new book. So you think you've got problems, which we'll deal with later. However, we're going to do a subtly different version now. Yeah, in my book. Can I talk about my book now? Later, later. OK, there are 100 prisoners, but you failed to come up with 100 prisoners. I gave it a go, and I ended up with 10 prisoners who are over here. Look at them all. I don't know what they did to end up in maths jail. But you know, maybe they might be able to get out of maths jail if they solve the puzzle. Oh, yes, right. So the puzzle, what are we going to do? So here we have 10 drawers. They are numbered from 1 to 10. We also have 10 cards. We've chosen the cards from 1 to 10. There we are. What we're going to do, we're going to shuffle the cards. So they're in a random order. We're going to place the 10 cards in the 10 drawers so that each drawer has one card and each of the cards from 1 to 10 is in its own drawer. And the next bit of the puzzle is, our maths criminals here, the maths prisoners, are going to come up one by one and open five drawers only. Look at the cards, put them back in. So they're going to look at, open one drawer, look at it, put it back, open another drawer, look at the card, put it back, do that five times. So they will have looked at exactly half the number of drawers that there are because there are 10 drawers. They're doing it five times. Then they will go over there. Okay, they're going to do that one after the other. They're going to do it 10 times. And they can't, like, change the cards? No, they can't change the cards. Make any notes, anything like that? No, they open it, look at it, put it back in exactly the same one. And if, this is the puzzle, if every single one of the prisoners manages to open a drawer and see the number, that is their own number, the number they have on, hang on, over there, around their necks, then... Everyone lives. Everyone lives. Maybe we can't even free them. But if at least one, so only one of these 10 people needs to fail to find their own number, can we kill them? I think we kill them all. I don't know what's more morally questionable, killing them all because someone failed or just absorbing them of whatever their crimes may be because they got a random... Oh, well, we'll find out. That's for the philosophy bit. Yeah, exactly. So, math-wise, what we're going to do is we're going to run this and see what happens. So, while they can't communicate during the puzzle, they can have a chat in advance. You're welcome to confer and come up with a strategy before we begin. Okay, I think they're pretty much ready over there. We're now joined by Matthew Scroggs, who's going to be our warden. You're going to bring them up one at a time, keep track of who sees their number and who doesn't, and then we'll run it a few times and see if we have any successful rounds. So, Alex and I are going to get out of the way. Okay, we're now on round five happening in the background, and unbelievably, so far, they've survived half the time, two from four. They're pretty good, pretty good prisoners, yeah. Okay, so obviously they've got a strategy or something, but just, like, naively, the odds, if they were picking randomly... You would not expect this at all, because if you're choosing five out of ten and you want to find your own number, the probability of you getting your own number is a half. Five over ten, a half, 50%. So, for all ten of them to do it, the probability is half times a half times a half, which is one over two to the ten, which is? One over 1024. Yeah, that brilliant fact, which is always very useful, is that two to the ten is about a thousand. 0.1%. 0.9% stuff. In other words, they have 99.9% chance of dying, only 0.1% of surviving, yet 50%. I mean, that is unbelievable. No way, if there's a one in a thousand chance, we would have had two from four already. But anyway, we'll keep going. We'll put some more rounds through, see how many they win. Obviously, there is a strategy. We're going to reveal that not long from now in the video. So, if you do want to try and work it out for yourself, either think very quickly now or pause and have a go. What are they doing? Okay, so they do actually have a strategy. They're not just picking at random. What are they doing? What they're doing, they're going, they know their own number. So, they're going to the draw of that number. So, if they're number five, they'll go to number five draw. They're looking at it. If it's the number five card there, they're saved, they're done. If not, it's another number. Then they go to the draw of that number. Oh, so here's five. That wasn't five. I think it was six. Oh, and then they've gone to seven. Because there would have been the seven card would have been in it. And then that tells them where to go next. And then they work their way around. And they do five of those. Exactly. They're only allowed to do it five times. So, they're doing five times. So, they're going on a kind of journey, which the next step of that journey is told to you by the card that they pull out the draw. And just by following that strategy, instead of being like a one in a thousand, you go to about a 30% chance, like one in three chance of everyone seeing their own number, which is unbelievably hard to realise that's true. We'll pull that apart in a moment. But for now, if you want to have a play and work out why this strategy works, have a go. Four. Here we go. Last card. Do they live or die? Ah, they're dead. Okay, so that's round 10. We're done. Unbelievably, they survived five out of 10 rounds. This is pretty amazing. Which is insane. But to see what was going on, we've left the draws from the last round where they didn't survive. So, we're going to follow their strategy. So, Alex, if you want to pull out the numbers for me, what have we got? Number one. Went to 10. Goes to 10. Number 10. Yeah. Goes to three. Yeah. Number three. Goes to five. Five, yeah. Number five. Yeah. Goes to six. Yeah. Number six goes to two. Yeah. Number two. Goes to eight. Oh my goodness, right, yeah. Number eight goes to four. Four. I'm running out of room. Number four. Well, I think we know where it has to go. Goes to seven. Yes. Seven goes to one. Oh, okay. That closes there. What are we missing? Nine. Goes to itself. Okay. We've ended up with one giant loop, and then a little one by itself. But most people didn't find their numbers. Yeah, they didn't because just say you got number six. Yep. You'd get two and draw six. Then you'd go to eight. Then four. Then seven. And you're only allowed to open five draws. So, that's five steps along the cycle. So, if the cycle has more than five numbers in it, which it does there, then anyone that has a number which is on the cycle is not going to find their number, I mean, and everyone's going to die. So. We also kept the cards from one of the rounds when everyone did survive. So, would you mind telling me how this one cycles through? And I'll put this one up. One would get ten. Ten, got it. Yep. Two goes to one. Three stays at three. Which goes to four. Must go to six. Nine's in ninth place, so nine goes to itself again. Okay, so that's all the networks we get for when they won. Yeah, there are five different cycles. And this is what we got when they didn't win. Very, very different. Yeah, so because the largest cycle there has three digits in, you know that whichever number you get within five steps, you're going to get back to yourself. And once you get back to yourself, that's equivalent of seeing your own number in the draw. Yeah. Freedom. And it happens to everyone. The genius thing is because you start with your number, you definitely start in the cycle which has your number. Correct. And if they're all smaller than five, everyone wins. Correct. So, the solution to the puzzle, the reason why this works is that you need to work out of the total possibility, the total permutation of cycles broken down with 10 digits, how many, what proportion have cycles that are largest with five digits in? Don't worry, we did that. Yeah. I sat down and wrote some Python codes to check every possible arrangement of cards in the draw, because that's how I do maths. And there are 3,628,000, don't laugh at that, 800 possible, it's just 10 factorial, I wouldn't have expected anything less. Now, of those 10 factorial possible arrangements, 1,285,920 of them have no cycles greater than five. And if and only if, I believe, there are no cycles greater than half the number of draws, everyone lives. Otherwise, someone's going to get it wrong. And Matthew Scruggs, who was our warden, went through and actually printed out every single possible combination of cycles and how likely they are. And one in 10 gives you all 10 in one giant loop. And actually, it's quite interesting to work out why you get that one tenth of the time. But we'll leave that as a bonus puzzle. And actually, Matthew's around here. He's got the breakdown from, these are official results as you're working out. Thank you. Thank you very much. And you can see in the final breakdown, there's roughly the same. It's a little bit off, although we did end up with more survival than we expected. Yeah, it should have been about three. Yeah. And we got five. That's true. If it's like about 35%, it's three or four. And so we got five. The gods were benevolent. Exactly. The prisoners got lucky. Mass jails let a lot of criminals loose. But actually, I ran the numbers properly. And even if you're using the strategy, it's still 50-50. So each individual prisoner still has exactly a 50-50 chance of finding their number. But the probabilities, they clump. So it just means, because you're using the strategy, it's no longer independent. And you go from a 1 in 1,000 chance to a 1 in 3. It's bonkers. For 10 prisoners and 10 draws, we ended up with a probability of success around 35%. For the original 100 prisoners, it's about 31%. And I did randomly sample when you've got 1,000 or 10,000 prisoners. I couldn't do it exhaustively like I did for 10. But if you simulate it, they all come in around 31%, as far as I can tell. And fun fact, nobody knows if, as you have more and more prisoners, it's going towards a limit or if it will eventually go down to zero or what. That's an open bit of mathematics. If you have a play with it and you find anything, please do let us know. So finally, thanks so much to the RI for having me in here and all the volunteers who helped out. And of course, thanks to Alex Bellos and his new book, So You Think You've Got Problems. So Alex is going to sign a whole load of these and we'll have them on mass gear. And if you buy it now or pre-order it on mass gear, I'm going to go through and I've got like a verified stamp. I'm going to verify that puzzle because we've double checked it and I'll sign that page as well. So if you order it straight away, you will get the limited edition verified version of Alex Bellos' new book. Just so you know why all these people are in mass jail. Divided by zero. Didn't show they're working out. Turned the eight key in their calculator upside down, honestly. Draws infinity as two circles next to each other. Some people get very upset about that for goodness knows reason. Disliked a three blue, one brown video. Honestly, Grant is an international treasure. Showed too much working out. That also gets you in here. Didn't pick a side on the pie versus towel debate, which is very upsetting. Writes their zeros as perfect circles. Also a serial killer. Those two go together. They're not unrelated. There you go. Says all of QED the long way each time, honestly. And just got caught up in a bad bunch. They round too much. They always round down as well, honestly.