I hope everybody's been having a great week given the circumstances! I have some really cool article ideas in the works over this time, so you can look forward to some exciting new GLeaM content! Especially as we're all doing online school right now, if you have any friends or family who might benefit from my articles, send it their way! This is one way for all of us to stay connected and engaged to some neat math while we're stuck in our homes, and I'd love it if you would post some topics to the forums as well, so we can have some dialogue. So without further ado, let's go into the article.
Today's article is an exploration of some of the coolest puzzles I've found. We'll look at the classic Prisoner's Dilemma and two other prisoner-related (but very different) problems. I urge you to try each of these puzzles before continuing. See what you can come up with first, then read what I have to say. The key to problem (or puzzle!) solving is perseverance. Think critically, explore different ideas, and you may surprise yourself with what solutions you can reach!
The Prisoner's Dilemma
I can't write a prisoner-themed article without the original prisoner puzzle.
Let's say there are two prisoners, Alice and Bob. The police think that either Alice or Bob has committed a crime, so they bring them in for questioning. The rules are as follows:
If Alice and Bob both stay silent, they each get one year in prison.
If Alice betrays Bob, she goes home free and Bob stays in prison for three years.
If Bob betrays Alice, he goes home free and Alice stays in prison for three years.
If both Alice and Bob betray each other, they both get two years in prison.
They are not given a chance to strategize before they have to make a decision.
Here's a screenshotted chart (all rights and courtesy to This Place) to help you see the situation more clearly:
Think about this for a second. What decision is best for the group? What decision is best for each individual? Can you see a paradox here? Only scroll down when you're ready.
Ok, I'll continue now.
Clearly, the best decision for the group is if they both cooperate. They would then only spend a combined two years in prison, as opposed to three or four as in the other situations.
However, if Alice considers what's best for her, she reaches a different conclusion. She reasons that if Bob stays silent, she should betray. Then, she'd go free instead of spending a year in prison. Similarly, she reasons that if Bob betrays, she should also betray. Then, she'd get two years instead of three years in prison. Either way, she should betray.
If Bob goes along the exact same line of reasoning, he also betrays. But then, even through logical reasoning, Alice and Bob end up at the situation the worst for the entire group—4 years combined in jail—and it's also worse for each individual than if they had both cooperated. This is the situation they'll pretty much always end up at unless they're given time in advance to strategize and they trust each other perfectly, and yet, it's far from ideal.
I pretty much can't give you a satisfying conclusion to this one, other than the neat paradox itself. This is the contradiction created between the conflicting interests of the group and the individual, and it's actually a situation super relevant in economics—it keeps prices low.
Say we're thinking about the beverage industry. Theoretically, Coca-Cola and Pepsi could both set high prices and make a lot of money if they cooperated. However, every customer wants the lowest price, and neither company trusts the other to not lower their prices below the margin they set and in turn steal most of the costumers. Therefore, they end up both having lower prices as they fight for the lowest price to dominate the business, a low-price position worse for both the beverage industry and both individual companies. (Note that since some companies realized this was happening and decided to work together to raise high prices in the market, the government has now actually made 'price-fixing' illegal.) And that's an application that came from a problem based on prisoners!
Here's an article that explains the situation even more (it uses a lot more complex math and economics but it's fascinating): www.investopedia.com/articles/investing/110513/utilizing-prisoners-dilemma-business-and-economy.asp
Here's the most popular video on the Prisoner's Dilemma. (The example they used here is with advertising, and they also make a cool point about rational agents):
I'll give you one more great video for good measure:
If you want another more complex variation, go here: https://www.youtube.com/watch?v=BOvAbjfJ0x0. This is called the Iterated Prisoner's Dilemma and uses many of the same ideas in an even cooler way.
The Hat Puzzle
This time, the only way to escape from prison is to pass this test.
You and nine other prisoners (a total of ten) are all wearing a hat that is either black or white. You all stand in a line facing forward so that everyone in the line can see the hats of everyone in front of them but none of the hats behind them and not their own hat.
None of you have any idea how many of each color hat there are.
The prison guard tells the group to guess one by one, starting from the back, the color of their own hat. You can only guess the color of the hats and can say nothing else or convey any other information. You're allowed to strategize before the game starts.
Is there a way to come up with a strategy that maximizes your odds of everyone guessing their hat correctly? (Hint: What if the words black or white imply some other information?)
More specifically, is there a way to always get at least nine of the hats right?
For this one, I'm just going to give you the link to the TED-Ed video on this concept, so I can focus more of my article on the last (and more mathy!) puzzle. This is a great puzzle though, and I highly recommend you think about it a lot before watching all the way to the solution. This one requires a bit of ingenuity, so you should feel highly accomplished if you solve it!
There are so many cool variations on this one, so learn more about this puzzle! Here's another video that shows you a couple of these variations and talks about the problem even more.
The 100 Prisoners
It's finally time for my favorite prisoner puzzle! The last two have been logic-based, which of course is still math, but this one is even more mathy, and I think it's a very surprising and exciting conclusion. This puzzle comes directly from Alex Bellos' new book, So You Think You've Got Problems, which is full of some of the best puzzles out there. I highly recommend this book (especially as you're stuck at home) because it has so many great ideas, problems, and activities (125 to be exact) for a stay-at-home-season.
A cabinet with a hundred drawers, each numbered from 1 to 100, stands in an otherwise empty room in a prison. The warden enters the room, writes down the names of 100 prisoners on separate pieces of paper, and distributes the pieces of paper randomly in the cabinet so that each drawer contains the name of one prisoner.
The warden exits the room and assembles the 100 prisoners whose names she wrote on the slips of paper. She tells them that they will each be let into the cabinet room, one after the other; once in there, they are permitted to open 50 drawers and look at the names on the pieces of paper inside. She adds that if every single prisoner opens the drawer containing his name, everyone will be freed. But if at least one prisoner doesn't open the drawer with his name in it, everyone will be killed.
The prisoners are allowed to think up a strategy before they go into the cabinet room, but once the first prisoner goes in, they are not allowed to communicate in any way. They cannot leave messages in the room, nor tell the prisoners what they saw once they leave the room.
What strategy should the prisoners use?
As before, think about it before you move onto my explanation. What's remarkable here is the odds seem super dim—if each person opens randomly, they each have a 1/2 chance for a grand total of 1/2^100 chance of success for the prisoners, a number that is basically zero—but the winning strategy here gives odds of more than 30% success!
Are you ready? Ok, let's tackle it.
Before I move on, let's think about the drawer as a whole, and let's stick to ten prisoners for the time being. Bear with me as I venture into a concept that might seem irrelevant for the moment, but it will all make sense when I reach our strategy.
Number the prisoners 1 to 10, so we can keep track of numbers instead of names. Then, the drawer could be arranged as follows.
DRAWER NUMBERS: 1 2 3 4 5 6 7 8 9 10
PRISONER NUMBERS: 4 7 10 2 6 5 1 3 8 9
Here, Prisoner 4's name is in drawer 1, Prisoner 1's name is in drawer 7, and so on.
This rearrangement of the numbers from 1 to 10 is called a permutation, and though it can be looked at as just a rearrangement of the numbers from 1 to 10, we can also look a different way: as several rearrangements.
For drawers 5 and 6, notice that all we did was rearrange the order of 5 and 6.
Notice, also that for drawers 1, 2, 4 and 7, all we did was rearrange the order of 1, 2, 4 and 7.
Therefore, we can pair this down to several cycles.
Namely,
1 → 4 → 2 → 7 → 1
3 → 10 → 9 → 8 → 3
5 → 6 → 5
Here, we say length is the number of numbers in the cycle, and we call each of the cycles a permutation cycle. Thus, we have two permutation cycles of length 4 and one of length 2 here.
Let me give you one more example to show you what I mean.
DRAWER NUMBERS: 1 2 3 4 5 6 7 8 9 10
PRISONER NUMBERS: 10 5 3 9 1 7 8 2 6 4
The cycles we get this time around are:
1 → 10 → 4 → 9 → 6 → 7 → 8 → 2 → 5 → 1
3 → 3
Here, we have one permutation cycle of length 9 and one of length just 1 (3 doesn't change at all!)
Do you get the concept I'm putting across here? We can do the exact same thing for 100 prisoners, and we're just thinking of drawer arrangements (i.e. what order the warden puts down the names in the drawers) in terms of cycles.
Now here's the strategy. Have Prisoner 1 look inside the first drawer. If they get their name, they're done! Otherwise, they can open the drawer corresponding to the prisoner whose name they drew. That means that if they get Prisoner k's name, they open Drawer k. For example, if Prisoner 1 opens the first drawer and gets Prisoner 32's name, they open Drawer 32. And so it continues. If in Drawer 32, Prisoner 1 gets Prisoner 67's name, they open Drawer 67, and so on. Here's an image to show you what I mean:
This is just equivalent to the cycles argument! The prisoner is sent along a path equivalent to a permutation cycle. Here's why: As we had shown above (for the case where there are only 10 prisoners), a permutation can be broken into cycles, and each prisoner traveling in this way from drawer to drawer progresses along the cycle. For example, in the first case, Prisoner 1 would go to Drawer 1 and get Prisoner 4's name, then Drawer 4 and get Prisoner 2's name, then Drawer 2 and get Prisoner 7's name, then Drawer 7 where they finally get their own name. This progresses along the cycle 1 → 4 → 2 → 7 → 1. If you don't believe me, test out a few more to see how this works. We can see what happens to all the other prisoners in both cases by simply looking at the cycles.
Why would this strategy theoretically increase the odds of success? Each prisoner already starts in a cycle that includes their own number! Instead of blindly stumbling around, they have a direction. And, if their cycle has a length of 50 or less, they will land on their number in less than 50 turns, which is all they need to succeed.
Therefore, the chances that the entire group of prisoners succeeds is just the chance that the random permutation placed in the drawers for them consists of only cycles of length 50 or less. (To illustrate this, in relation to our two cases with 10 prisoners, the first case would work and the second would not.)
Unfortunately, the math to go about calculating this is a little too complicated for this article (one of the best ways of doing it is just having a computer crunch the numbers), but trust me, the odds here are just over 30 percent, which is a lot more than random chance. Here, your chances of success are almost a third! It's this interesting property of numbers (and permutations) that saves the prisoners here (or at least gives them a decent chance of survival)!
I'd definitely recommend Alex Bellos' book because he does an amazing job of explaining this, and there's also a great video on standupmaths that first introduced me to this problem. They actually test it out in real life, so it's really cool to watch!
Here's an article you can read about it as well: http://datagenetics.com/blog/december42014/index.html (It has some better graphics than I do, so it might help clarify my argument!)
That's it for today! I hope everybody enjoyed these three prisoner-themed puzzles. To be honest, I didn't really realize until right now that this might have a relation to our current situation in "house arrest"; I was just excited to share some really cool puzzles! Perhaps my subconscious might have latched onto that :) Stay safe, stay healthy, and don't give up on math! I'll be back next week with another cool article.
There is an easy solution for the first one. Make Alice and Bob less selfish. Easy!