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 Tom Hanrahan, some big-money game show strategizing:
You are a contestant on “Who Wants to Be a Riddler Millionaire.” You have already made it to a late round: You could walk away right now with $250,000. But there are two potential questions still to go that you can try to answer. You could earn $500,000 if you get one right and then walk away, or $1 million if you nail them both. If you attempt any answer and miss, you go home with $10,000.
Luckily, you still have two of your lifelines:
- The 50/50: The host reduces the four possible answers to two; one of them is the correct one and the other is randomly chosen from among the other three answers.
- Ask the Audience: The studio audience submits their own guesses. You know historically that the correct answer will be chosen by the plurality 50 percent of the time; while 30 percent of the time the right answer finishes second; 15 percent third; and 5 percent last. Additionally, if there are only two answers available to the audience, they pick the correct one more often 65 percent of the time.
The problem: You’re burned out. All the pressure and questions you’ve already answered have made you a babbling mess. You assess that you would have no clue on the last two questions, so you’ll be guessing randomly.
What is your best strategy to play, or stop, or use your lifelines to maximize your expected winnings?
Riddler Classic
From Jerry Meyers, a conundrum timed to kick off the football season!
My son recently started collecting Riddler League football cards and informed me that he planned on acquiring every card in the set. It made me wonder, naturally, how much of his allowance he would have to spend in order to achieve his goal. His favorite set of cards is Riddler Silver; a set consisting of 100 cards, numbered 1 to 100. The cards are only sold in packs containing 10 random cards, without duplicates, with every card number having 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?
What if he decides to collect the more expansive Riddler Gold set, which has 300 different cards?
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Bridger Conklin ÑÑâÐ of Washington, D.C., winner of last week’s Riddler Express!
Last week, Riddler Nation had just legalized sports betting, and everyone was excited to bet on the national pastime: competitive coin flipping. Every coin-flipping match is between two teams. Each team selects a two-coin sequence of heads and/or tails to look for, and they simultaneously flip their own coin over and over until one team finds its sequence. (If both teams find their sequences at the same time, they start over and flip until only one team finds it.) First to be the only team to have found its sequence wins.
When you arrived, you saw that the Red Team had chosen the sequence “heads-tails,” and the Blue Team had chosen “heads-heads.” You can get even odds on either team. Which team should you put your money on?
If you like winning, you should bet on the Red Team and its head-tails sequence.
Understanding why the Red Team has an advantage might be easiest if we’re armed with a diagram. Solver Paul Sim wrote in to share his, shown below.
Each branch of the tree depicts a flip of either heads or tails, and a team’s victory along a given path of branches is highlighted with that team’s color. The Red Team has six victories possible in these first four flips, while the Blue Team has only four. “The Red Team’s natural advantage,” Paul wrote, is “in being able to overlap their failures with their next attempt.”
Solver Steven Fellows shared another way to visualize this solution, shown below. Each team starts the game at the top of the flowchart, flips the coin and follows the steps shown. The Blue Team’s disadvantage can be see by the long arrow up the left-hand side of its chart. If the Blue Team fails to get its second head, it must go back to the beginning of the game, in essence. If the Red Team fails to get its tail, it only needs to go back one step.
According to the simulations of many solvers, all of this means that the Red Team wins this game about 59 percent of the time — a good deal for your even-money bet.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Peter Wiggin ÑÑâÐ of San Francisco, winner of last week’s Riddler Classic!
Last week, Acey and Deucy wanted to play a game of Nim. An example game goes like this: Two players start with three heaps — one with three counters, one with four counters and one with five counters. They take turns choosing a heap and removing counters — at least one counter, but they can also take multiple counters or the whole heap. The player who takes the last counter from the last heap wins.
The problem was that Acey and Deucy were experts at this game, and knew that with perfect play, the player who went first was guaranteed to win. Boring! But they still wanted to play, so they introduced some randomness. They’d roll three dice, and use those three numbers to determine the number of counters placed in the three piles to start the game.
But this randomized Nim game still gives an advantage to one of the players. To make this random-start game actually fair, if Acey goes first, how much should Acey bet against Deucy’s nickel?
Acey should wager 40 cents.
That’s because Deucy is eight times less likely to win than Acey. There are 6×6×6 = 216 different games of Nim these two might play, given the rolls of the three dice. With perfect play, the first player will win 192 of these games. That’s 192 wins to 24 losses for Acey, or a ratio of 8-to-1. Therefore, Acey’s 40 cents wagered against Deucy’s nickel would be a fair bet.
The somewhat trickier bit is to figure out why 192 of the games are wins for the first player. One way to get there would be through an exhaustive computer search of the 216 games, and Ziling Zhou shared an example. Another would be to think about the idea of “nim-sum,” which in this case transforms the dice’s numbers into binary and adds them up without carry. Because the two players take turns, converting things into binary helps us solve the puzzle. For example, the nim-sum of rolls of 5 and 3 is 101 + 011, without carry, which equals 110, or 6. It has been proven that the first player in a game of Nim is guaranteed to win so long as the nim-sum of a given game is not zero. The sum is zero in the following games: (1,2,3), (1,4,5), (2,4,6) and (3,5,6). There are 3×2×1 = 6 ways to roll each of those four games, for a total of 24 wins for Deucy, and 192 wins for Acey.
Good luck, Deucy.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.