Can You Take Down All The Bottles Of Beer?
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.
Riddler Express
This week’s Express comes just in time for Super Bowl LVII:
In football, a touchdown is worth six points, a one-point conversion is worth one point, a two-point conversion is worth two points, a field goal is worth three points and a safety is worth two points.2 A team may attempt a conversion only after it has scored a touchdown, and it must decide whether to attempt a one-point conversion or a two-point conversion.
Some methods of scoring points are more common than others. So when a team has scored 14 points, it’s safe to assume that they scored two touchdowns and two one-point conversions. But that’s not necessarily how those 14 points were scored.
Using the aforementioned methods of scoring, how many distinct ways can a team score 14 points? Note that the sequence in which a team scores these points doesn’t matter here. So scoring a field goal and then a safety is the same as a safety and then a field goal (i.e., there is only one distinct way a team can score 5 points).
Extra credit: Using the aforementioned methods of scoring, how many distinct ways can a team score 28 points?
Riddler Classic
From Steven Brown comes a puzzle to take down and pass around:
You and your friends are singing the traditional song, “99 Bottles of Beer.” With each verse, you count down the number of bottles. The first verse contains the lyrics “99 bottles of beer,” the second verse contains the lyrics “98 bottles of beer,” and so on. The last verse contains the lyrics “1 bottle of beer.”
There’s just one problem. When completing any given verse, your group of friends has a tendency to forget which verse they’re on. When this happens, you finish the verse you are currently singing and then go back to the beginning of the song (with 99 bottles) on the next verse.
For each verse, suppose you have a 1 percent chance of forgetting which verse you are currently singing. On average, how many total verses will you sing in the song?
Extra credit: Instead of “99 Bottles of Beer,” suppose you and your friends are singing “N Bottles of Beer,” where N is some very, very large number. And suppose your collective probability of forgetting where you are in the song is 1/N for each verse. If it takes you an average of K verses to finish the song, what value does the ratio of K/N approach?
Solution to the last Riddler Express
Congratulations to 👏 Ryan Calkin 👏 of Lathrup Village, Michigan, winner of last week’s Riddler Express.
Last week, you were playing darts and trying to maximize the number of points you earned with each throw. You were deciding which sector to aim for. Your dart had a 50 percent chance of landing in that sector and a 25 percent chance of landing in one of the two neighboring sectors. Reading clockwise, the sectors were worth 20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12 and 5 points, as shown below. (For the purposes of this puzzle, you didn’t have to worry about the bullseye, the outer ring that was worth double or the inner ring that was worth triple.)
Which sector should you have aimed for to maximize your expected score?
This was a relatively straightforward computation. You could have targeted any of the 20 sectors, and for each sector you had to add 50 percent of that sector’s value plus 25 percent of the values for both neighboring sectors.
Now the average value of all the sectors was the sum of the numbers from 1 to 20 divided by 20, or 1/20*20(21)/2, or 10.5. Surely it was possible to do better than that.
Aiming for the 16-point sector did fairly well. Half of 16 plus a quarter of 7 plus a quarter of 8 resulted in an expected score of 11.75 points. Meanwhile, both the 19-point and 14-point sectors were better targets. Half of 19 plus a quarter of 3 plus a quarter of 7 resulted in an expected score of 12 points. And half of 14 plus a quarter of 9 plus a quarter of 11 similarly resulted in 12 points.
But the best sector to aim for was the 7-point sector. Half of 7 plus a quarter of 16 plus a quarter of 19 resulted in an expected score of 12.25 points. While the individual sectors ranged from 1 to 20 points, the expected scores formed a much tighter distribution around the mean of 10.5, ranging only from 8.75 to 12.25 points.
For extra credit, you had to “fairly” (by some definition of fair for you to define) assign the point values around a dartboard in some other way. Solver Michael Greenberg worked under the assumption that you still had a 50 percent chance of hitting your target sector and a 25 percent chance of hitting either neighbor. Michael then sought to have all 20 expected values be as close as possible to the average of 10.5.
He immediately realized they couldn’t all equal 10.5, since targeting the 20-point sector (with minimal neighbors worth 1 and 2 points) resulted in an expected score of 10.75 points. But Michael still came up with the following ordering of sectors: 20, 1, 19, 3, 17, 5, 15, 7, 13, 9, 11, 10, 12, 8, 14, 6, 16, 4, 18 and 2. The 20-point and 10-point sectors both had an expected score of 10.75 points, while the 11-point and 1-point sectors both had an expected score of 10.25 points. The remaining 16 sectors were right on target, with an expected score of 10.5 points. As noted by solver Emily Kelly, this arrangement decreased the standard deviation of the expected scores by an order of magnitude. Not bad!
Solution to the last Riddler Classic
Congratulations to 👏 Bill Neagle 👏 of Springfield, Missouri, winner of last week’s Riddler Classic.
Last week, you took TikTok’s #blindletterchallenge. You were presented with five letters, one at a time. Letters were picked randomly, but you could assume that no two letters were the same (i.e., letters were picked without replacement). As each letter was presented, you had to identify which of five slots you’d place it in. The goal was for the letters in all five slots to be in alphabetical order at the end.
For example, consider an attempt at the challenge by Michael DiCostanzo. The first letter is X. Since this occurs relatively late in the alphabet, he puts this in the fifth slot. The second letter is U. He puts that in the fourth slot, since it also comes relatively late (and the fifth slot is already occupied). Next, the third letter is E. He takes a gamble, and places E in the first slot. The fourth letter is D. Since D comes before E alphabetically, but no slots prior to E are now available, Michael loses this attempt.
If you played with an optimal strategy, always placing letters in slots to maximize your chances of victory, what was your probability of winning?
Solvers Izumihara Ryoma, Austin Shapiro and Mark Girard all started with a more general version of the problem. Instead of 26 letters and five slots, they considered L letters and S slots. Let’s write P(L, S) as the probability of winning this general version of the game using the optimal strategy. Suppose the first letter presented to you is xth in the sequence of letters, so that x = 1 for A, x = 2 for B, and so on. If you were to put this letter in the ith slot, what would be your probability of winning?
Well, you would need a few things to go right. First, among the remaining S-1 letters to be picked, you needed i-1 of those to come earlier in the alphabet than xth to occupy the first i−1 slots, noting that there were x−1 such letters. You also needed S–i letters to come later in the alphabet than xth to occupy the last S−i slots, noting that there were L–x such letters. The probability of both of these occurring was x−1 choose i−1 multiplied by L−x choose S−i, divided by L−1 choose S−1 — i.e., all the ways to choose among the L−1 letters for the remaining S−1 slots.
But that wasn’t all you needed to go right. Placing this first letter correctly did not guarantee victory. You still had to correctly place the remaining S−1 letters appropriately. In other words, you had to correctly place letters in the first i−1 slots (among x−1 potential letters) and you had to correctly place letters in the last S−i slots (among L−x potential letters). The probability of the former was P(x−1, i−1) and the probability of the latter was P(L−x, S−i). The probability of them both happening was the product of these.
Returning to the first letter you were presented with, we had said you placed it in the ith slot. But what was the optimal value of i? It was the one that maximized your overall probability of winning from that point on, i.e., the value of i that maximized (x−1 choose i−1) × (L−x choose S−i) / (L−1 choose S−1) × P(x−1, i−1) × P(L−x, S−i).
But wait, there’s more! You didn’t know what letter you would be presented with, which meant x was equally likely to be anywhere from 1 to L. Summing that previous expression over all values of x and dividing by L gave your optimized probability of winning the challenge.
With this formula in hand, you could use recursion or dynamic programming to calculate P(L, S) for small values of L and S, making use of edge cases like P(n, n) = 1 and P(L, 1) = 1. The TikTok #blindletterchallenge had 26 letters and five slots. Therefore, the probability of winning with the optimal strategy was P(26, 5), or about 25.43 percent.
If you enjoyed this puzzle, check out some of the extra credit proposed by the puzzle’s submitter, Angela Zhou (a few of which have been answered by Mark):
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.
