As many famous math riddles go, somewhere out there, a king is bored, and of course what better way to pass the time than to mess with his prisoners? He thinks to himself, "I have this big headgear collection with 10 types of items and I have 10 prisoners. I have an idea!
" He goes to his prisoners and tells them, "Hey prisoners! Check out these 10 types of cranial accessories that I have. Soon my servants will bring in lots of each type so we can play a game.
Each of you will get one type of head accessory but we'll cover your eyes when we put it on you so you won't know which type you got. You might all get a different type, all the same type, or any mix and match. Then you'll turn around and see everyone and everything in this room except what's on your own head.
If I see any secret communication from that point forward, the game is over. I want to completely avoid any information passing so I'm going to wait a bit, snap my finger, and I want you all to declare your hat type at the same exact time. I'm feeling really generous today, so if any of you is right, you all get to leave.
Feel free to talk it out until the full stash of hats arrives. What should the prisoners do? Believe it or not, these prisoners can guarantee, yes guarantee, that they will all get out.
And this is not clickbait. There is no weird solution like hidden mirrors or word games. There's a legitimate mathematical strategy that will guarantee that at least one of the prisoners is right no matter what.
In fact, the king and whoever else is there could hear the prisoners discuss their strategy, and the prisoners will still get out no matter what. If that sounds impossible, good. It'll make the solution even more awesome.
And minor detail: I know you can tell the difference between wearing a cap, a helmet, and a pair of glasses. Just please suspend your disbelief and pretend they all feel exactly the same. There are only so many emojis I have to work with here.
So here's the riddle in summary: 10 prisoners are shown 10 types of hats. They are told all of the following: Once the full stash of hats arrives, there is no communication whatsoever. Everyone gets one aforementioned type of hat but doesn't know which.
Everyone gets to see everyone else's hats. Everyone gets some time to think upon seeing everyone else's hats. On signal, everyone must declare a hat type.
If anyone declares their own hat type, everyone wins. The prisoners may strategize before the full stash of hats arrives. What strategy could the prisoners use to guarantee their escape?
I encourage you to pause and try to find the strategy on your own. But maybe you're stuck. In fact, I often hear, "I don't get how this puzzle is possible.
No matter what strategy you use, each prisoner has exactly a 10% chance of being right. " Well, let me help you move forward just a little with math riddle solving tip #1: Look at a simpler form of the problem. What if it was just two prisoners and two types of hats?
Let's say a cap and a top hat. How would those two prisoners strategize? If you give yourself a chance, I'm convinced you can figure this one out.
It's much easier than the general problem. This is even a fun riddle for kids that they can legitimately solve but may have to think for a bit before they see the solution. If you're ready to see the solution for this simpler problem, without further ado, here are the four possible scenarios: We'll have one prisoner say the same type of hat as he sees on the other and the other prisoner will say the opposite type of hat than what he sees on the other.
This always works because they either have the same type of hat or a different type of hat, so one of them has to be right. Now this is great, but how do you extend the strategy to 3, 10, or even 100 prisoners and hat types? I encourage you to pause again and try this on your own, but if you're stuck, let me help you just a little with math riddle solving tip #2: Ask a different but related question.
Sometimes looking at the problem differently will give you tools that are essential to its solution. Other times, looking at the problem differently gives you some unique insight that although not strictly necessary, makes the problem much easier. It's like in video games.
In some games, you start with nothing and you need to upgrade to the legendary armor of Legend Land in order to fight the final boss. In other games, you can technically run to the final boss in your underwear and win because you're just that good at the game, but more likely you'll pick up some weapons along the way that will help you slay the boss much more easily. One thing we might ask: what happens if there's no strategy?
Let each prisoner choose randomly. There's certainly nothing the king or anyone can do to ruin this strategy, so at least we have that going for us. Now this brings us into the realm of probability, while the original problem seems to have nothing to do with probability, but let's see where this takes us.
To find the probability that at least one prisoner gets the right answer, we will take 1 minus the probability that all prisoners are wrong. Since each prisoner's choice is independent, the probability that all prisoners are wrong is just the probability that any given prisoner is wrong multiplied out by itself for each prisoner. Finally, the probability that a given prisoner is wrong is one minus the probability that he's right, so in our original riddle, where there are 10 prisoners, the probability of an individual prisoner being right is 10%, or 1/10, so the probability of at least one prisoner being right is (1-1/10)^10.
If we look at this in general for any number of prisoners, it's (1-1/N)^N. What does this look like as the number of prisoners and hat types gets higher and higher? If you're familiar with the number e, this might start to ring a bell.
e is defined as the limit as N approaches infinity of (1+1/N)^N. And it turns out that e^x is just the limit as N goes to infinity of (1+x/N)^N, so if we set x to -1, we get a limit of e^-1, or 1/e. Now we're almost there.
Our initial expression had a 1 minus, so let's move some limits around and here we go. The probability of prisoner success if they all guess randomly tends towards 1-1/e as N gets bigger, and for 10, it's already a good approximation. It comes out to about 2/3.
Now 2 out of 3 isn't bad, but how do we promote that to a guarantee? Well, one thing we can ask ourselves is why we have to calculate the probability by asking the inverse question: What's the probability of everyone being wrong? Why couldn't we just have directly computed the probability of someone being right?
We could have, but it would have been complicated. If I say, "Tell me the probability that prisoner 1 or prisoner 2 is right," it's not just the sum of the individual probabilities, because I have to account for the possibility that they're both right. For example, if I tell you that there's a 50% chance of rain and 60% chance of strong wind, it doesn't mean there's a 110% chance of rain or strong wind.
It means there is possible overlap that will get counted twice if we just add the probabilities. So if there's, say, a 40% chance of both, then the probability of either is 50 + 60 - 40, or 70%, and a 30% chance of neither. It was the same way when we reduced the puzzle to two prisoners.
Imagine if they would have chosen randomly. There was a 50% chance of either being right but a 25% chance that both could be right, so there was also a 25% chance that neither is right, meaning only a 75% chance of success. And with more prisoners, it gets more complicated, as there are more and more overlaps to deal with, and this remaining roughly 1/e of space where all prisoners are wrong.
So yes, we could have computed the probability directly, but it would have been complicated. There would be a few options. We could have either computed some mutually exclusive events like exactly one prisoner being right, or exactly two, or exactly three, and so on, so there are no overlaps to worry about, or we could have added the probabilities of each individual prisoner being correct, but then actually account for all the little overlaps and the overlaps within the overlaps and the overlaps within the overlaps within the overlaps, and so on, which is a huge mess.
Now, if you stare at this, you might see what's coming. Feel free to pause, but otherwise here we go. When people say, "I don't see how this puzzle is possible.
No matter what strategy you use, each prisoner has exactly a 10% chance of being right. ", I have to hold back a smile, because I'm thinking, "Yes! That's exactly right.
And that's your ticket to finding a solution. " There is no way an individual prisoner can have anything other than a 10% chance of being right and there's nothing they can do to increase or decrease that chance, so if we look at our equation for the probability, the only way to get a 100% chance of success is to remove all these little potential overlaps. It's precisely because more than one prisoner can be correct that allows for the possibility that they can all be wrong.
Only when the overlaps are gone do we get guaranteed success. Our puzzle has a massive red herring. It's asking us to guarantee at least one prisoner right, when it could equivalently be asking to guarantee no more than one prison right.
This is a much simpler question and this is in fact what we did when we solved the case of two prisoners: One assumes the hats are the same type, and the other assumes they're different types, so it's impossible for both of them to be right. And I'd like to really hammer this point. Notice how we didn't change either prisoner's odds of being correct.
It's 50/50 no matter what. What we changed is how we orient those odds in a new space of possibilities so that they take up all the available space. You might even think I was not being precise with my words when I said we need to just guarantee no more than one prison right, because out of context, you could ask, "What if that guarantee makes zero prisoners right?
" But no, those words are precise because there is no way to force them to all be wrong. No matter how you rearrange these blobs of probability, every prisoner has a 10% chance. If you merely guarantee that there is no overlap, those 10 blobs of 10% chance must create a 100% chance, and the moment there is any overlap, there must be space for the possibility of all the prisoners being wrong.
So for our problem, we need to find some property of the overall setup that has 10 mutually exclusive scenarios, and make each prisoner give an answer that assumes a different one of those scenarios. At this point, I also want to share a very small math riddle solving tip #3: Translate the obscure into the familiar. In other words, think of unfamiliar objects in terms of familiar objects.
This one's kind of obvious, but the types of hats can be anything that has 10 distinct elements, like hats of different colors, or even numbers. As they plan their strategy, the prisoners can map each hat type to a number, and the problem can be viewed in terms of those numbers. Now take one final chance to pause and remember: You're not trying to make at least one prisoner right.
You're just trying to make sure that no more than one can be right. Ready? Here's the strategy.
First, let's take every type of hat and assign it a number. From now on, when we see something like this, we think of it as something like this. Now imagine for a second that you're not one of the prisoners.
You're the king himself or some other third party observer. Let's say you add up all the numbers. Then you take the remainder of the sum when dividing by 10.
The particular case of 10 works very nicely. The remainder when dividing by 10 is just the last digit of the sum. Now no matter what arrangement of hats anyone will ever make, the remainder after summing and dividing by 10 is just one of the digits 0 to 9.
Furthermore, the scenarios are exclusive. Any given arrangement has only one of the 10 possible remainders. The prisoners don't know what the full sum is, but let them each assume that it has a different remainder.
Now there can't possibly be more than one right, and in fact, there must be exactly one right. Each one just uses the number that would force the total sum to be his presumed remainder. And of course, they say hat types at the end, not numbers, so they have to map their decided number back to a hat type by just inverting their original mapping of hat types to numbers.
Let's see this all in action. The prisoners look like this so they think of each hat type as a unique number from 0 to 9 that they chose for their strategy. They also each chose a unique assumed remainder for the sum of all the hats.
Once the hats are on, it's time to execute the strategy. Let's first look at this from the perspective of the prisoner who assumes that the remainder is 0, meaning the total sum is a multiple of 10. He has no clue what his number is, but if he adds up all the other numbers, he gets 52, so to complete the assumption that the arrangement has a remainder of 0, he's thinking 8, because that would make the system have a sum of 60, which has a 0 remainder when divided by 10.
He's wrong, because his number was actually 6, but that's no problem. There's still another nine prisoners. Let's do this again for the next prisoner, who assumes that the arrangement has a remainder of 1.
He sees a sum of 53 and wants a remainder of 1, so he's thinking 8 as well. He's also wrong. The third prisoner sees a sum of 53, but wants a remainder of 2, so he's thinking 9.
Still wrong. Now let's go on fast forward and do all the prisoners with assumed remainders 3, 4, 5, 6, 7, 8, and 9. Now the prisoners map their answers back to hat types.
Then, when they get the signal, the prisoners simultaneously call out their guesses and triumphantly find that exactly one of them is correct. Finally, the prisoners used their puzzle solving skills, and with the assistance of a segue into probability, they outsmarted the king and they get to leave. At this point I should of course point out how there's nothing special about 10 prisoners.
If there are N prisoners and N hat types, just replace 0 to 9 with 0 to N-1. In fact, that's exactly what we were doing when we had two prisoners The prisoner assuming both hats are the same is assuming that the total sum remainder, after division by 2, is 0, and the prisoner assuming both hats are different is assuming the total sum remainder, after division by 2, is 1. Another way to think of it is that the hats create a base N number system and then the remainder is always the last base N digit.
Then you don't need any mappings, but good luck thinking in terms of new digits. Also, we kept asking throughout this video, "what number do I add to X to make the remainder be Y when divided by N? " The mathematical shorthand representing that concept is called (Y - X) mod N, so for example when we said something like, "What number do I add to 53 to make the remainder be 2 when I divide by 10?
", that was just asking what's (2 - 53) mod 10, and the answer of course was 9. I'd also like to say that I think there's a lesson in all this. We like to say that the whole is not just the sum of its parts, but in riddles like this, we can see it formally.
An individual prisoner has a 1/N chance of being right no matter what. There's absolutely no way whatsoever to get around it. But if you put together N prisoners in the same exact conundrum, they can guarantee a correct answer.
So too we should never underestimate what amazing things a group of friends or a community can accomplish, despite the challenges faced by the individuals. Here's to friends, family, and community. Let's continue to work together, and in particular, to push each other forward in the right direction.
Let's make the impossible possible.
