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 next week’s 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.
Last Sunday we lost Alex Trebek, a giant in the world of game shows and trivia. The show he hosted over the course of four decades — Jeopardy! — has previously appeared in this column. Today, it makes a return.
You’re playing the (single) Jeopardy! Round, and your opponents are simply no match for you. You choose first and never relinquish control, working your way horizontally across the board by first selecting all six $200 clues, then all six $400 clues, and so on, until you finally select all the $1,000 clues. You respond to each clue correctly before either of your opponents can.
One randomly selected clue is a Daily Double. Rather than award you the prize money associated with that clue, it instead allows you to double your current winnings or wager up to $1,000 should you have less than that. Being the aggressive player you are, you always bet the most you can. (In reality, the Daily Double is more likely to appear in certain locations on the board than others, but for this problem assume it has an equal chance of appearing anywhere on the board.)
How much money do you expect to win during the Jeopardy! round?
Extra credit: Suppose you change your strategy. Instead of working your way horizontally across the board, you select random clues from anywhere on the board, one at a time. Now how much money do you expect to win during the Jeopardy! round?
The solution to this Riddler Express can be found in the following week’s column.
From Angela Zhou comes a bad football puzzle. The puzzle’s great, but the football is bad:
Football season is in full swing, and with it have been some incredible blown leads. The Atlanta Falcons know a few things about this, not to mention a certain Super Bowl from a few years back. Inspired by these improbabilities, Angela wondered just how likely one blown lead truly is.
The Georgia Birds and the Michigan Felines play a game where they flip a fair coin 101 times. In the end, if heads comes up at least 51 times, the Birds win; but if tails comes up at least 51 times, the Felines win.
What’s the probability that the Birds have at least a 99 percent chance of winning at some point during the game — meaning their probability of victory is 99 percent or greater given the flips that remain — and then proceed to lose?
Extra credit: Instead of 101 total flips, suppose there are many, many more (i.e., consider the limit as the number of flips goes to infinity). Again, the Birds win if heads comes up at least half the time. Now what’s the probability that the Birds have a win probability of at least 99 percent at some point and then proceed to lose?
The solution to this Riddler Classic can be found in the following week’s column.
Solution to last week’s Riddler Express
Congratulations to 👏 Christoph 👏 of Southampton, United Kingdom, winner of last week’s Riddler Express.
Last week, FiveThirtyEight’s editor Santul Nerkar completed two 20-mile runs on a treadmill while training for the New York City Marathon. For the first run, he set the treadmill to a constant speed so that he ran every mile in 9 minutes.
The second run was a little different. He started at a 10 minute-per-mile pace and accelerated continuously until he was running at an 8-minute-per mile pace at the end. Moreover, Santul’s minutes-per-mile pace (i.e., not his speed) changed linearly over time. So a quarter of the way through the duration (in time, not distance) of the run, his pace was 9 minutes, 30 seconds per mile, halfway through it was 9 minutes per mile, etc.
Which training run was faster (i.e., took less time) overall? And what were Santul’s times for the two runs?
The first run wasn’t particularly tricky. If Santul ran 20 miles and each mile took 9 minutes, then he ran for a total of 180 minutes, or 3 hours.
It was the second run that tripped a few readers up. His initial pace was 10 minutes per mile, meaning he was running 6 miles per hour. His final pace was 8 minutes per mile, or 7.5 miles per hour. At this point, you might have assumed that his speed steadily (i.e., linearly) increased from 6 to 7.5 miles per hour. But that was not the case!
As the problem stated, it was Santul’s minute-per-miles pace that steadily decreased (i.e., he sped up) from 10 minutes per mile down to 8 minutes per mile. If it took him T minutes to run the 20 miles, then his pace after t minutes was 10−2t/T minutes per mile. (You can check that this equals 10 when t = 0, and 8 when t = T.) If his pace was 10−2t/T minutes per mile, then what was his speed? It was 60/(10−2t/T), which gave you the correct units of miles per hour.
At this point, you knew Santul’s speed as a function of time. To figure out how long he was running for, you had to integrate this speed over time — yes, you needed calculus — and you had to set that equal to 20, his distance in miles. This is precisely what solver Eli Wolfhagen did, and solving this integral for T gave the correct answer: 2/(3·ln(5/4)) hours, or about 179.26 minutes. Accelerating this way meant that Santul ran about 45 seconds faster, which can feel like an eternity when running a marathon.
No matter how he trained, I think it’s fair to say that Santul ran one hell of a race!
Solution to last week’s Riddler Classic
Congratulations to 👏 Nick Meyer 👏 of Oakland, California, winner of last week’s Riddler Classic.
Last week, inspired by John von Neumann, you tried to simulate a fair coin using a biased coin that had a probability p of landing heads.
Suppose you wanted to simulate a fair coin in at most three flips. For which values of p was this possible?
Von Neumann’s approach worked for any value of p, but didn’t guarantee a simulation that lasted a finite number of flips. However, for certain values of p, it was indeed possible to simulate a fair join in just a few flips.
Of course, with one flip there was only one way to simulate a fair coin — when p was 1/2.
With two flips, things got a little more complicated. When p was 1/2, you could still simulate a fair coin (e.g., the same outcome on both flips could simulate heads, while different outcomes simulated tails). But there were two other values of p that were also possible. When p was 1/√2, the probability of getting two heads (HH) was 1/2, while the probability of getting anything else (HT, TH or TT) was also 1/2. You could similarly simulate a fair coin when p was 1−1/√2, in which case the probability of getting TT was 1/2.
So with two coin flips, there were three values of p that could be used to simulate a fair coin: 1/2, 1/√2 and 1−1/√2. Just one problem — the riddle asked about three flips, not two. But at this point, your strategy was set. You were looking for different ways to cobble together different outcomes so that their combined probabilities equaled exactly 1/2.
With three coin flips, there were eight total outcomes:
- HHH, which had probability p3
- HHT, HTH and THH, which each had probability p2(1−p)
- HTT, THT and TTH, which each had probability p(1−p)2
- TTT, which had probability (1−p)3
From here, it was a matter of adding these probabilities together and seeing when these sums equaled 1/2. In all, there were 64 ways to combine them: p3, p3 + p2(1−p), p3 + 2p2(1−p), etc. Here are all 64 polynomials plotted when p was between 0 and 1:
It’s a little hard to see from the graph (solver David Lewis zooms in on a similar graph), but there were 19 locations where these curves cross the 0.5 mark, meaning there were 19 distinct values of p that could simulate a fair coin in at most three tosses. Solver Josh Silverman used a combinatorial approach to count up the solutions without needing to find them all, while Emma Knight was able to list them all out.
For extra credit, you were asked to simulate a fair coin in at most N flips, rather than just three flips. For how many values of p is this possible?
We already saw that for one flip, there was one value of p. For two flips, there were three values. And for three flips, there were 19 values. Brave souls who looked at four flips found there were 271 possible values of p, while there were 8,635 values for five flips and 623,533 values for six flips. As it often turns out in this column, there was an OEIS sequence for that… but wait a minute — solver Tracy Hall just posted this sequence last weekend, meaning it was a brand new discovery. Amazing!
Solver Angela Zhou decided to plot a histogram showing all 623,533 values of p that could yield a fair coin in at most six flips:
There’s a lot of mathematical richness to unpack there, like the chasm surrounding 0.5 (although 0.5 is itself a solution), not to mention all those other peaks and valleys.
It’s hard to compete with von Neumann, but Riddler Nation has definitely given him a run for his money.
Want more riddles?
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 firstname.lastname@example.org