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.
First, an unlucky puzzle that comes a week late:
Depending on the year, there can be one, two or three Friday the 13ths. Last week happened to be the second Friday the 13th of 2020.
What is the greatest number of Friday the 13ths that can occur over the course of four consecutive calendar years?
Extra credit: What’s the greatest number of Friday the 13ths that can occur over a four-year period (i.e., a period that doesn’t necessarily begin on January 1)?
The solution to this Riddler Express can be found in the following column.
From Patrick Lopatto comes a riddle we can all be thankful for:
To celebrate Thanksgiving, you and 19 of your family members are seated at a circular table (socially distanced, of course). Everyone at the table would like a helping of cranberry sauce, which happens to be in front of you at the moment.
Instead of passing the sauce around in a circle, you pass it randomly to the person seated directly to your left or to your right. They then do the same, passing it randomly either to the person to their left or right. This continues until everyone has, at some point, received the cranberry sauce.
Of the 20 people in the circle, who has the greatest chance of being the last to receive the cranberry sauce?
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Nathan Ainslie ÑÑâÐ of Bloomington, Indiana, winner of last week’s Riddler Express.
Last week, you were a contestant on the TV show Jeopardy! You were competing in the (single) Jeopardy! round and your opponents were simply no match for you. You chose first and never relinquished 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 selected all the $1,000 clues. You responded to each clue correctly before either of your opponents could.
One randomly selected clue was a Daily Double. Rather than award you the prize money associated with that clue, it instead allowed you to double your winnings (up to that point) or wager up to $1,000 should you have less than that. Being the aggressive player you are, you always bet the most you could have. (In reality, the Daily Double was more likely to appear in certain locations on the board than others, but for this problem you assumed it had an equal chance of appearing anywhere on the board.)
How much money did you expect to win during the Jeopardy! Round?
There were a total of 30 clues on the board, and any one of those 30 clues could have been the Daily Double. That meant there were 30 cases to consider: when the Daily Double was the first clue you selected, when it was the second clue, the third clue, and so on. And when it was one of the first six clues selected, the Daily Double was worth $1,000; otherwise, it doubled your money. (Technically, if it was the sixth clue, it was worth $1,000 and doubled your money, since you had won exactly $1,000 by that point.)
Many solvers listed out all 30 cases and averaged the winnings. Alternatively, you could have added up the total amount of prize money across all the cases and then divided by 30. Across these cases, each clue was the Daily Double once, which meant it wasn’t the daily double 29 times. Adding up the values of all the clues — without worrying about the Daily Double — gave you 6·(200 + 400 + 600 + 800 + 1000), or $18,000, which meant that 29 boards of clues were worth $522,000.
Now to add up the Daily Doubles. As we already said, for the first six cases the Daily Double was worth $1,000. When the Daily Double was the seventh clue, it was worth $1,200. From there, its value increased by $400 until it was $3,600 as the 13th clue. Then, it increased by $600 until it was $7,200 as the 19th clue. Next, it increased by $800 until it was $12,000 as the 25th clue. Finally, it increased by $1,000 until it was a whopping $17,000 as the 30th and final clue. That was some James Holzhauer wagering right there.
Even without a spreadsheet, you needed some hefty addition to tally up these Daily Doubles. Their total value across the 30 cases turned out to be $192,000 — roughly 36 percent of what the non-Daily Double clues had been worth.
Combining the regular clues with the Daily Doubles gave a sum of $714,000 for all 30 cases. That meant the average — the amount you’d “expect” to win — was $23,800.
For extra credit, instead of working your way horizontally across the board, you selected random clues from anywhere on the board, one at a time. Now how much money did you expect to win during the Jeopardy! Round?
This was a much thornier version of the problem. First, there were five rows in which the Daily Double might have appeared. Then, for each row, you had to consider the order in which you worked your way across the board. So instead of 30 cases, there were in fact 5·30!/((6!)45!), or about 4.1×1019 cases to consider.
From here, most solvers used Monte Carlo methods, simulating the game of Jeopardy! thousands or even millions of times to approximate the answer. As a few brave coders (like Josh Silverman, Lowell Vaughn and Alex Vornsand) found the answer was approximately $26,150. (This was quite close to the result you’d get — $26,146.67 — if you assumed every clue had been worth the average amount of $600. The answer was slightly larger than this, since the Daily Double more than doubled your winnings whenever you had less than $1,000.)
It made sense that picking clues randomly would net you more winnings on average, because you now had a greater chance of selecting higher-value clues (like the $800 and $1,000 rows) before hitting the Daily Double.
For this puzzle, we’ll let Alex Trebek have the last word. We miss you.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Alex Zorn ÑÑâÐ of Brooklyn, New York, winner of last week’s Riddler Classic.
Last week, you modeled blown football leads, something the Atlanta Falcons know a thing or two (or three) about. The Georgia Birds and the Michigan Felines were playing a game in which a fair coin was flipped 101 times. In the end, if heads came up at least 51 times, the Birds won; but if tails came up at least 51 times, the Felines won.
What was the probability that the Birds had at least a 99 percent chance of winning at some point during the game — meaning their probability of victory was 99 percent or greater given the flips that remained — and then proceeded to lose?
This was a challenging riddle, to be sure. For starters, you first had to make sense of what it meant to have “at least a 99 percent chance of winning,” while avoiding the tempting answer of 1 percent. Before any flips were made, the Birds had a 50 percent chance of winning. But suppose, through incredible luck, that the first 50 tosses all came up heads. From there, the Birds could still technically lose if the final 51 tosses all came up tails — an event whose probability was 1/251.
That was just one (albeit very unlikely) way for the Birds to have a 99 percent chance of winning and then blow the game. But there were many other, more likely scenarios, each of which involved an excess of heads flipped toward the beginning. One way to add up the probabilities of these scenarios was to analyze (preferably via code) what was happening at each combination of wins (W) and losses (L) for the Birds.
Here’s a graph that shows the pairs (W, L), shown in red, from which the Birds had at least a 99 percent chance of winning. You could determine these directly using combinatorics, or working backwards recursively, noting that the probability of winning from (W, L) was the average of the probabilities from (W+1, L) and (W, L+1).
Next, you wanted to find the probability that the Birds passed through at least one of the red locations in the graph above. That is, for each (W, L), what was the probability that at some point the Birds had a 99 percent chance of winning?
This graph was very similar to the first. But there were some places — in green and aqua — where the Birds had ventured into the 99 percent region and then back out. These paths through the graph were what made it possible for the Birds to blow their lead.
From here, you had to focus on which of these paths resulted in an overall loss for the Birds, and work backwards. The final graph below shows the Birds’ chances of reaching a 99 percent chance of victory at some point and then blowing the lead, for each (W, L).
These chances were greatest when the Birds had won 50 games and lost 51, when there was a roughly 2 percent chance that they had blown a 99 percent lead somewhere along the way. Working backwards, their chances of blowing a lead when they had zero wins and zero losses were about 10 times smaller, or 0.21 percent. This was the solution to the riddle: the Birds’ chances of at some point having a 99 percent chance at victory and then proceeding to lose.
For extra credit, instead of 101 total flips, there were many, many more (i.e., you had to consider the limit as the number of flips went to infinity). Again, the Birds won if heads came up at least half the time. Now what was the probability that the Birds had a win probability of at least 99 percent at some point and then proceeded to lose?
To solve this, some coders continued increasing the number of flips beyond 101 and looked for asymptotic behavior. This week’s winner, Alex Zorn, approached the extra credit analytically by first defining three key probabilities:
- h, the probability that the Birds ever hit 99 percent win probability
- c, the probability that the Birds choke after attaining their 99 percent win probability
- w, the probability that the Birds hit 99 percent and go on to win
With these three variables defined, Alex was able to set up a few equations. For example, w = 0.99·h and c = 0.01·h, since that’s what was meant by a 99 percent win probability. Moreover, the probability that the Birds were the ultimate winners was 0.5, which had to equal w. That meant h = 50/99, which in turn meant that c — the probability of blowing that 99 percent lead, was 1/198.
Finally, solver Allen Gu noticed some rather peculiar oscillating behaviors as the number of coin flips increased and the threshold for “choking” was closer to 50 percent:
Personally, I’d be very curious to see this plotted on a logarithmic graph. My hunch is that the oscillations are due to the discrete nature of the problem, when the border between the yellow and blue regimes in that first graph shifts.
In any case, I have been informed that the Birds are doing a little better as of late. Those Los Angeles Lightning Bolts, on the other hand … not so much.
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