Problem: (Thank you to Mr. Schwartz in 9th grade for this). In the classic TV game show, "Let's Make a Deal," you win a prize if you can choose which of three doors the big prize is behind. After choosing the door, the host opens one of the other doors which has a booby prize (like a bag of sand). You are then asked whether you want to switch to the one remaining closed door, or stick with your original choice. Should you switch?
Solution:
Let's start with a drawing of the situation. Pic 1 shows the basics where there are three closed doors, two with booby prizes and one with the big prize behind it. We are asked to choose any door first. Let's say we choose door 2.
Then, the host opens another door, let's say door 1, revealing a booby prize (e.g., a bag of sand). We are then asked if we want to switch -- from door 2 to door 3. We know that one of the remaining closed doors has the big prize, and one another booby prize This situation is shown in pic 2.
Well, should we switch?
The obvious answer is that it just doesn't matter. We know that there is a prize behind one of two doors, and we have a 50% shot. So, switch or don't switch; we should be indifferent and we will have a 50% chance of winning regardless of strategy.
This is a fairly straight-forward answer and is tempting. However, before we accept it, let's think about the situation a little more and if we're using all available information.
Certainly, if we were presented with two doors and told to choose 1, we could make an overwhelming case for the strategy not mattering -- similar to the strategy not mattering if you call heads or tails on a fair coin toss.
However, we were given lots more information here with a longer set up, one choice, some information revealed, and then asked to make another choice.
Unless your an information/logic expert, a good strategy is to try some examples to see what happens when we choose different doors (with big prize, without) and what happens when we switch/don't switch to see if it helps us figure out the optimal strategy:
Strategy 1: Never switch
A- Choose big prize door out of three (chance 1/3)
- Don't switch when given choice
- Win
- Chance: 1/3
B-Choose booby prize door (chance 2/3)
- Don't switch when given choice
- Lose
- Chance 2/3
Strategy 2: Always switch
A-Choose big prize door out of three (chance 1/3)
- Switch when given choice
- Lose
- Chance 1/3
B-Choose booby prize door out of three (chance 2/3)
- Switch when given choice
- Win
- Chance 2/3
See if these examples help you figure out what to do.
To win:
- If we never switch, we have a 1/3 chance of winning; we need to choose the correct door initially
- If we always switch, we have a 2/3 chance of winning; we need to choose the incorrect door initially
Hence, we should always switch to improve our odds of winning.
This answer is correct, but there's something that can be unsatisfying about it, because intuitively, staring at two doors -- which is our situation, it still feels like we should be able to choose either and have a 50% chance.
So, why isn't this the case?
Well, we were given significant information by the door that was opened. Since the door had to be either: 1) the other booby prize (if we chose the first), or 2) could be either other door, we are given information because it cannot simply be a random door that was opened. This information can be used to improve our odds by switching.
If you're interested there are lots of simulations run showing the benefits of switching vs. not switching.
This is a good example of the first, intuitive answer of 50% not being correct, which is usually the case in brainteasers. When stumped, try doing examples, and when possible, the exhaustive answer set, as that can help bring insights into the correct solution.
/* Please let me know if you find bugs or have alternative solutions. Thank you, Noah */
Code WorkOut of the Day -- Daily exercises for programmers looking for jobs, or just to keep sharp with skills and have fun. I give talks, like this: https://youtu.be/NpvTE7GlXSM for people looking for jobs, or groups of programmers preparing for M&A tech HR due diligence. Follow us on twitter: @codewod
How to
When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!
This was the topic of conversation at a recent dinner party. It can be challenging to persuade someone who is convinced that switching doesn't matter.
ReplyDeleteTurns out the easiest way for people to wrap their mind around it, was to think of how bad their first guess was. Once they realized their first guess was wrong most of the time (66%), it was a obvious conclusion to always switch.
Mythbusters did a great visual of this. Start watching around 14:00 http://www.youtube.com/watch?v=Ytv-_RB4xWI
ReplyDeleteI love it! Mythbusters is great.
Delete