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.