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.
Find all pairs of integers a and b that are solutions to the following equation: a·(a+1)·(a+2) = b2+4.
That’s it. That’s the riddle.
One cloudless night, the sky above you contains an equal number of visible stars and planes. Suddenly, you spot a point of light at a particular angle of elevation above the horizon. Based purely on this angle, you want to determine whether the point of light is more likely to be a star or a plane.
While figuring this out, you make the following simplifying assumptions:
- Earth is a perfect sphere with a radius of 4,000 miles.
- Stars are equally likely to be anywhere in the night sky.
- Planes are equally likely to be flying anywhere over Earth (i.e., not just limited to established air routes) at an altitude of 6 miles. You can neglect takeoffs and landings.
After some quick thinking, you realize that at this particular angle, the point of light is equally likely to be a star or a plane. What is this angle of elevation?
Solution to the last Riddler Express
Congratulations to 👏 Christian Wolters 👏 of San Jose, California, winner of last week’s Riddler Express, which came just in time for Super Bowl LVII.
In football, a touchdown is worth 6 points, a point after touchdown (PAT) is worth 1 point, a 2-point conversion is worth 2 points, a field goal is worth 3 points, and a safety is worth 2 points.2 A team may attempt a conversion only after it has scored a touchdown, and it must decide whether to attempt a PAT or a 2-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 PATs. But that’s not necessarily how those 14 points were scored.
Using the aforementioned methods of scoring, how many distinct ways could a team have scored 14 points? Note that the sequence in which a team scores these points didn’t matter. So scoring a field goal and then a safety was the same as a safety and then a field goal (i.e., there was only one distinct way a team could score 5 points).
Suppose a team scored A touchdowns, B PATs, C 2-point conversions, D field goals and E safeties. Then the problem became finding the number of distinct ordered quintuples (A, B, C, D, E) such that 6A + B + 2C + 3D + 2E = 14, with the constraints that A, B, C, D, E ≥ 0 and B + C ≤ A (i.e., a team couldn’t have more conversions than touchdowns).
A few solvers wrote computer code to count up the number of such quintuples. But for those counting by hand, like organizing your thinking based on the number of touchdowns (A) was a good strategy, since touchdowns were worth the most points. There were three cases to consider: when A was 2, 1 or 0.
When A was 2, you somehow needed to account for 2 remaining points (with at most two conversions). There were three ways to do this: with two PATs, with one 2-point conversion and with one safety.
When A was one, you needed to account for 8 remaining points (with at most one conversion). Here, you could look at subcases when D (the number of field goals) was 2, 1 or 0. When D was 2, that again left 2 points remaining, either due to a 2-point conversion or a safety. When D was 1, that left 5 points remaining. The only way to account for this odd number of points was with two safeties and a PAT. And when D was 0, that left 8 points remaining. The two ways to generate 8 points were with four safeties or with three safeties and a 2-point conversion.
Finally, when A was 0, you needed to account for all 14 points without any conversions. At this point, you were left with the somewhat simpler equation 3D + 2E = 14, which had three non-negative integer solutions: D = 4 and E = 1, D = 2 and E = 4, and D = 0 and E = 7. (Ah yes, the seven-safety game!)
In the end, there were 11 ways to score 14 points. Again, here were all 11 ordered quintuples (A, B, C, D, E):
- (2, 2, 0, 0, 0)
- (2, 0, 1, 0, 0)
- (2, 0, 0, 0, 1)
- (1, 0, 1, 2, 0)
- (1, 0, 0, 2, 1)
- (1, 1, 0, 1, 2)
- (1, 0, 0, 0, 4)
- (1, 0, 1, 0, 3)
- (0, 0, 0, 4, 1)
- (0, 0, 0, 2, 4)
- (0, 0, 0, 0, 7)
There were also other ways to arrive at the same solution. For example, to account for the constraint that B + C ≤ A, solver Andrea Andenna considered a touchdown and its corresponding conversion attempt as a single unit, worth either 6, 7 or 8 total points.
For extra credit, you had to similarly count the number of distinct ways a team could score 28 points. This was tougher to count by hand, and at this point most solvers, like Adnan Haque, resorted to computer assistance. It turned out there were 57 ways a team could score 28 points. (And yes, one of those ways was to score a whopping 14 safeties.)
Solution to the last Riddler Classic
Congratulations to 👏 Malachi Elkins 👏 of Huntsville, Alabama, winner of last week’s Riddler Classic.
Last week, you and your friends were singing the traditional song, “99 Bottles of Beer.” With each verse, you counted down the number of bottles. The first verse contained the lyrics “99 bottles of beer,” the second verse contained the lyrics “98 bottles of beer,” and so on. The last verse contained the lyrics “One bottle of beer.”
There was just one problem. When completing any given verse, your friends had a tendency to forget which verse they were on. When this happened, you finished the verse you were currently singing and then went back to the beginning of the song (with 99 bottles) on the next verse.
For each verse, suppose you had a 1 percent chance of forgetting which verse you were currently singing. On average, how many total verses did you expect to sing?
This sort of puzzle, with probabilities of moving from one state to another and a “final” absorbing state (i.e., the end of the song) was readily solved with a Markov chain. To construct a transition matrix, you knew that each verse (with n bottles) had a 99 percent chance of transitioning to the next verse (with n−1 bottles) and a 1 percent chance of transitioning back to the first verse (with 99 bottles).
You could equivalently have used this information to set up a rather large system of equations. Solver Mike Strong defined E(n) as the expected number of verses when starting with n bottles. Here, E(n) = 1+ 1/100·E(99) + 99/100·E(n−1). Plugging in 99 for n and rearranging gave the equation E(99) = E(98) + 100/99. Similarly, E(98) = E(97) + (100/99)2, E(97) = E(96) + (100/99)3 and so on. Next, working backwards from the fact that E(0) = 0, Mike found that E(99) = 100/99 + (100/99)2 + (100/99)3 + … + (100/99)99.
This sum came to approximately 170.47, which was indeed the expected total number of verses. (Due to some ambiguity in the puzzle regarding whether you could forget while singing the last verse, I accepted any answer that was close to 170.) A number of solvers, including David Ding and Clement Lelievre were able to confirm this result via simulation.
For extra credit, you and your friends were singing “N Bottles of Beer” instead of “99 Bottles of Beer,” where N was some very, very large number. Your collective probability of forgetting where you were in the song is 1/N for each verse. If it took an average of K verses to finish the song, what value did the ratio of K/N approach?
Generalizing Mike’s equations, you now had the recursive relation E(n) = 1+ 1/N·E(N) + (1−1/N)·E(n−1). Working through the system of equations, you ultimately had E(N) = N/(N−1) + [N/(N−1)]2 + [N/(N−1)]3 + … + [N/(N−1)]N. This was a finite geometric series, and dividing this sum by N gave you the expression [N/(N−1)]N−1. This might not have looked like much, but it could be rewritten as [1+(1/(N−1)]N−1. In the limit as N went to infinity, subtracting 1 from N in the dominator made negligible difference, which meant the first term in the expression approached e. And so, as N increased, K/N approached e−1, or approximately 1.71828.
Solver Laurent Lessard plotted how the expected number of verses approaches this limiting ratio as N increased:
So forget “99 Bottles of Beer.” From now on, you and your friends will be singing “99 Bottles of B-e-r.” (Sorry, that was a terrible joke.)
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 firstname.lastname@example.org.