Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,1 and you may get a shoutout in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
From Adam Moses, a colorful competition:
Abby and Beatrix are playing a game with two six-sided dice. Rather than having numbers on the sides like normal dice, however, the sides of these dice are either red or blue. In the game they’re playing, Abby wins if the two dice land with the same color on top. Beatrix wins if the colors are not the same. One of the dice has five blue sides and one red side.
If Abby and Beatrix have equal chances of winning the game, how many red and blue sides does the other die have?
Riddler Classic
From Dan Johnston, a rich, profitable and meta-mathematical saga:
An eccentric billionaire has a published a devilish math problem that she wants to see solved. Her challenge is to three-color a specific map that she likes — that is, to color its regions with only three colors while ensuring that no bordering regions are the same color. Being an eccentric billionaire, she offers $10 million to anyone who can present her with a solution.
You come up with a solution to this math problem! However, being a poor college student, you cannot come up with the $10,000 needed to travel to the billionaire’s remote island lair. You go to your local bank and ask the manager to lend you the $10,000. You explain to him that you will soon be winning $10 million, so you will easily be able to pay back the loan. But the manager is skeptical that you actually have a correct solution.
Of course, if you simply hand the manager your solution, there is nothing preventing him from throwing you out of his office and collecting the $10 million for himself. So, the question is: How do you prove to the manager that you have a solution to the problem without giving him the solution (or any part of the solution that makes it easy for him to reproduce it)?
Extra credit: What if the billionaire’s challenge was a different type of problem? Are there other types of problems that you can prove you can solve without giving away the solution?
Solution to last week’s Riddler Express
Congratulations to 👏 Bradley Albrecht 👏 of Sherwood Park, Alberta, winner of last week’s Riddler Express!
Last week, you were a contestant on “What Wants to Be a Riddler Millionaire.” You’d done well and made it far: You could have walked away with $250,000, or you could have pressed on and answered up to two more questions. You would win $500,000 if you answered the first question and walked away or $1 million if you got them both right. However, if you answered any question incorrectly, you’d go home with just $10,000.
You also still had two of your lifelines: the 50/50, which randomly reduces the four possible answers to two, and the Ask the Audience, which polls the studio audience to give you more information about what the correct answer probably is.
If you assessed that you’d have no idea what the correct answer to those final two questions would be, what was your best strategy to maximize your expected earnings from this game show?
Let’s walk through a few options. As a baseline, what if you just walk away immediately? That one’s easy: Your expected earnings are $250,000.
If you press on, you should definitely try to use both of your lifelines — they will only help you. But how should you use them? There are three options. First, we could use one lifeline on the initial question and the other on the second, if we get that far. It doesn’t matter in which order we employ these in this case — using each individually gives us a 50 percent chance at answering a given question correctly, which gives us a 25 percent chance of winning the whole million. Therefore, your expected winnings with this strategy are (.75)($10,000) + (.25)($1,000,000) = $257,500 — a little better!
Now let’s say we decide to use both lifelines on the $500,000 question. That brings us to the second of our three strategies: Use the 50/50 and then Ask the Audience on the first question remaining. According to the parameters of the puzzle, the audience chooses correctly between two options 65 percent of the time. So your expected winnings in this case are (0.35)($10,000) + (0.65)($500,000) = $328,500 — better still! (Note that, if you do get that $500,000 question right, it doesn’t make mathematical sense to continue without any lifelines.)
Finally, there’s our third strategy: Use the Ask the Audience and then the 50/50, picking whichever answer the audience had prefered between the two remaining answers. According to the parameters of the puzzle, there is a 50 percent chance that the audience chose the correct answer, in which case we are guaranteed to answer correctly. There is a 30 percent chance that the audience’s second most popular answer was correct, in which case there is a two-thirds chance that the 50/50 will eliminate the most popular, incorrect answer. There is a 15 percent chance that the audience’s third most popular answer was correct, in which case there is a one-third chance the 50/50 will eliminate the more popular, incorrect answers. And there is a 5 percent chance that the audience’s least popular answer was correct, in which case we will never win. Summing this up, you’ve given yourself a \((0.5) + (0.3)(0.\bar{6}) + (0.15)(0.\bar{3}) = 0.75\) chance of answering the $500,000 question correctly. That gives you expected winnings of (0.25)($10,000) + (0.75)($500,000) = $377,500 — the best yet!
So to summarize, your best strategy is to use your Ask the Audience, then use your 50/50, then guess at the $500,000 question. If you get that one right, just walk away.
Solution to last week’s Riddler Classic
Congratulations to 👏 Sam Knott 👏 of Twickenham, England, winner of last week’s Riddler Classic!
Last week brought a collector’s financial quandary: My son recently started collecting Riddler League football cards and planned on acquiring every card in the set. This raised the question, naturally, of how much allowance he would have to spend to achieve his goal. His favorite set of cards was Riddler Silver, consisting of 100 cards. The cards are only sold in packs containing 10 random cards, without duplicates, and every card number has an equal chance of being in a pack. Each pack can be purchased for $1. If his allowance is $10 a week, how long would we expect it to take before he has the entire set?
It’ll take him about 50 packs, or five weeks’ worth of allowance.
This problem is a twist on the classic coupon collector’s problem. Here’s one way to think about the dynamics involved. With the first pack we buy, each card is guaranteed to be unique to us, so we will get 10 unique cards of the 100 total cards in the set. With the second pack we buy, each card has a 90 percent chance of being unique, since we already have 10 of the 100 cards, so one of the new cards is expected to be a duplicate. With the third pack, each card has an 81 percent chance of being unique, since we expect to already have 19 of the 100 cards. And so on. The more we collect, the harder it becomes.
After deploying some numeric or programmatic methods — as provided by solvers Jeremy Hummel and Andrew Hallacy, for example — we find that we can expect our complete collection to take about 50 packs, or five weeks. This process is obviously pretty inefficient. We’ll have to buy about 500 total cards to collect the 100 unique ones we want.
Solver Hernando Cortina illustrated his simulations of the number of unique cards that are acquired as one buys more and more packs. Unsurprisingly, as we’ve seen, the unique cards add up very quickly when you start out, but the more cards you have, the harder it becomes to find new ones.
As a bonus, I asked how long it would take if a kid was interested in collecting the Riddler Gold set, which consisted of 300 different cards. That’d take about 19 weeks’ worth of allowance. (It takes buying nearly 1,900 cards to collect the 300 you want.) Solver Laurent Lessard, in addition to providing a thorough analysis of the math behind this collecting problem, illustrated how long it would take (on the y-axis) to collect a given set of cards of some size (on the x-axis) based on how big each pack of cards was (the colors of the lines):
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.