The Final Battle For Riddler Nation
Illustration by Guillaume Kurkdjian
Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the 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 the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter or send me an email.
All good things …
Friday, June 30, will mark the final column for The Riddler here at FiveThirtyEight. But this isn’t quite the end.
I am pleased to announce that the mathematical puzzling will continue on Substack, beginning July 7. You can tune into my forthcoming newsletter, Fiddler on the Proof, affectionately known as “The Fiddler.” I’m hoping to make some more exciting announcements about this soon. But in the meantime, sign up (for free!) to keep the puzzle goodness going.
In the meantime, back to this week’s puzzle, which will be very familiar to many of you!
This Week’s Riddler
Some readers may be familiar with the first, second, third, fourth, fifth, sixth and seventh Battles for Riddler Nation. If you missed out, you may want to consult the thousands of attack distributions from some of these previous contests.
This week marks the eighth (and final!) such competition. As with the last few battles, I am once again tweaking the rules.
In a distant, war-torn land, there are 10 castles. There are two warlords: you and your archenemy. Each castle has its own strategic value for a would-be conqueror. Specifically, the castles are worth 1, 2, 3, … , 9 and 10 victory points. You and your enemy each have 100 soldiers to distribute, any way you like, to fight at any of the 10 castles. Whoever sends more soldiers to a given castle conquers that castle and wins its victory points. If you each send the same number of troops, you split the points. You don’t know what distribution of forces your enemy has chosen until the battles begin. Whoever wins the most points wins the war.
Submit a plan distributing your 100 soldiers among the 10 castles. Once I receive all your battle plans, I will adjudicate all the possible one-on-one matchups. A victory will be worth one “victory point,” while a tie will be worth 0.5 victory points. After all the one-on-one matchups are complete, whoever has accumulated the fewest victory points will be eliminated from the tournament, after which the battle will recommence with one fewer competitor.
If two warlords are tied with the fewest number of victory points, the first tiebreaker will be whoever has more wins (and fewer ties) and the second tiebreaker will be performance in the preceding round (and then the round before that, etc.). If two or more strategies on the chopping block are precisely the same, I will randomly pick which one to eliminate.
Whoever survives every round will be crowned the last king or queen of Riddler Nation!
Solution to the last Riddler Express
Congratulations to 👏 Matt Carlton 👏 of Los Osos, California, winner of last week’s Riddler Express.
Last week, two teams were starting a competition with the flip of a coin and a roll of a die. That is, one team’s captain flipped a coin while the other team’s captain rolled a die. They continued doing this until the coin was the same (whether heads or tails) for three consecutive flips or the number that was face-up on the die was the same for two consecutive rolls.
On average, how many coin flips did it take to get three in a row? And how many die rolls did it take to get two in a row?
Let’s start with the coins, which was arguably the trickier of the two. Suppose the expected number flips needed to get three in a row from the outset was E(0). Similarly, let’s call the expected number of remaining flips to get three in a row when the current sequence ended in one in a row — regardless of whether that was heads or tails — was E(1), two in a row was E(2) and three in a row was E(3).
From there, solver Emilie Mitchell set up a system of equations between these values, allowing her to solve for each of them. Since the goal was to get three in a row, E(3) was simply zero — you didn’t need any additional flips to get three in a row. Working backwards, when your sequence of flips ended with two in a row, your next flip gave you a 50 percent chance of getting three in a row and a 50 percent chance of reverting to just one in a row. Mathematically, that meant E(2) was equal to 1+E(1)/2.
Meanwhile, when your sequence of flips ended with one in a row, your next flip gave you a 50 percent chance of getting two in a row and a 50 percent chance of reverting to just one in a row. Mathematically, that meant E(1) = 1 + E(2)/2 + E(1)/2. Finally, when you hadn’t yet flipped even once, your first flip was guaranteed to give you one in a row. Mathematically, this meant E(0) = 1 + E(1).
Combining these equations gave you E(3) = 0, E(2) = 4, E(1) = 6 and E(0) = 7. And so, on average, it took the first captain seven flips to get three heads or tails in a row.
Now for the die. After the first roll, the probability of getting two in a row was 1/6 for every subsequent roll. That meant the probability of getting two in a row in two rolls was 1/6, in three rolls it was (5/6)ᐧ(1/6), in four rolls it was (5/6)2ᐧ(1/6), and so on. The expected number of rolls was therefore 2ᐧ(1/6) + 3ᐧ(5/6)ᐧ(1/6) + 4ᐧ(5/6)2ᐧ(1/6) + 5ᐧ(5/6)3ᐧ(1/6) + …. The sum of this arithmetic-geometric series turned out to be 7.
And so, on average, it took the second captain seven rolls to get two in a row.
I for one thought it was pretty neat that these two events — three in a row for flip with two outcomes and two in a row for a roll with six outcomes — occurred after the same number of attempts, on average.
But for extra credit, you were asked which event was more likely to occur first. It was tempting to think that both were equally likely to occur first, since they both occurred with the same average number of attempts. However, their probability distributions — that is, the probability with which they first occurred after a given number of attempts — were markedly different, as illustrated by solver Josh Silverman:
Sampling these two distributions revealed that two in a row for the die was more likely to come first, with a probability of 29/59, or about 49 percent of the time. By comparison, three in a row came first for the coin with a probability of 25/59. And, as you might have surmised at this point, they occurred at the same time with probability 5/59.
Solution to the last Riddler Classic
Congratulations to 👏 Gary M. Gerken 👏 of Littleton, Colorado, winner of last week’s Riddler Classic.
Last week, you studied the “middle-square method” for generating four-digit pseudorandom numbers (numbers that appear random, but are derived in a deterministic sequence).
According to this method, you started with a four-digit number, such as 9,876. When you squared it, you get the eight-digit number 97,535,376. Your next pseudorandom number was taken from the middle four digits of that square: 5,353. And to get the next pseudorandom number, you squared 5,353, which gives you 28,654,609, the middle four digits of which were 6,546.
Of course, many four-digit numbers had a square that’s seven digits rather than eight. And in a sequence of middle-square numbers, you’d likely encounter smaller numbers whose squares had six or fewer digits. In these cases, you could append zeros to the beginning of the square until you had eight total digits, once again taking the middle four digits.
No matter what initial four-digit number you picked, your sequence of pseudorandom numbers would eventually repeat itself in a loop. If you wanted the longest sequence of such numbers before any repetition occurred, what starting number should you have picked? And how many unique numbers were in the sequence?
Many puzzles in this column require analytical acumen, whereas others require computational cleverness. (In my opinion, some of the very best puzzles require both.) This puzzle definitely erred on the side of computation, as there were 10,000 possibilities to test (from the digits 0000 up through 9999) and no clear intuition into which four-digit numbers most gradually descended into a cycle. Virtually every solver wrote code or used a digital spreadsheet to find the answer.
Solver Michael Branicky’s Python code correctly determined the answer was 6,239, which resulted in a whopping 111 unique numbers. The final four unique numbers in that sequence were 4,100, 8,100, 6,100 and 2,100, which together formed a four-number loop.
Solver Tom Conroy made a directed map that shows the broader structure at play here:
Tom found that there were three four-number cycles and five fixed points (i.e., numbers whose middle-square resulted in themselves), the most surprising of which turned out to be 3,792, whose square is 14,379,264. Based on Tom’s graph, it appeared that the majority of four-digit numbers fell into the same eventual loop as 6,239 did.
Want more puzzles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email Zach Wissner-Gross at riddlercolumn@gmail.com.
