Can You Outthink The Sphinx?

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,¹ 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.

Riddler Express

The winners of the 2021 Regeneron Science Talent Search were announced on March 17. (Full disclosure: I was a finalist in this very same competition exactly one eternity ago. You can find me among a gaggle of fellow New Yorkers, if you look closely.)

I am delighted that two of this year’s winners were able to share their favorite puzzles for this week’s column!

Hailing from Portland, Oregon, high school senior Wenjun Hou took a swing at the famed knapsack problem with an algorithm designed to run on a quantum computer. This week, he’s putting quantum mechanics aside and challenging you to a classical game instead:

You and Wenjun are playing a game in which you alternate taking turns, removing pennies from a pile. On your turn, you can remove either one or two pennies from the pile. On Wenjun’s turn, he can remove either two or three pennies. Whoever takes the last penny loses. (If there is only one penny left and it’s Wenjun’s turn, then he skips his turn, which means you will lose). Suppose both you and Wenjun play optimally.

1) If you go first, then what initial numbers of pennies mean you will win the game?

2) If Wenjun goes first, then what initial numbers of pennies mean he will win the game?

The solution to this Riddler Express can be found in the following column.

Riddler Classic

Timothy Qian of Rockville, Maryland, was another winner of this year’s Science Talent Search. Like Wenjun, Timothy’s work related to quantum computing — he analyzed the bounds on how much information you can glean from a quantum system. And it just so happens that his favorite puzzle, developed with fellow student Gabriel Wu, is all about leveraging the information in a game to maximize your winnings:

You will be asked four seemingly arbitrary true-or-false questions by the Sphinx on a topic about which you know absolutely nothing. Before the first question is asked, you have exactly $1. For each question, you can bet any non-negative amount of money that you will answer correctly. That is, you can bet any real number (including fractions of pennies) between zero and the current amount of money you have. After each of your answers, the Sphinx reveals the correct answer. If you are right, you gain the amount of money you bet; if you are wrong, you lose the money you bet.

However, there’s a catch. (Isn’t there always, with the Sphinx?) The answer will never be the same for three questions in a row.

With this information in hand, what is the maximum amount of money you can be sure that you’ll win, no matter what the answers wind up being?

Extra credit: This riddle can be generalized so that the Sphinx asks N questions, such that the answer is never the same for Q questions in a row. What are your maximum guaranteed winnings in terms of N and Q?

The solution to this Riddler Classic can be found in the following column.

Solution to last week’s Riddler Express

Congratulations to 👏Samuel Zurier 👏 of Providence, Rhode Island, winner of last week’s Riddler Express.

Last week, you tried your hand at two riddles most “foul.” In NCAA men’s basketball, when a team has committed between six and eight fouls in a half, the opposing team is “in the bonus.” This means that the next time they are fouled while not in the act of shooting, they get to shoot at least one free throw. If the player makes that first free throw, they get to shoot a second. If either free throw is missed, one team will rebound the ball, and play will continue with the rebounding team in possession.

For last week’s Riddler Express, you were the coach of a team playing an opponent that was in the bonus. You could assume that they scored exactly 1 point per offensive possession, a figure that accounted for multiple shots if they rebounded their own miss (or misses) on a single trip, and that they rebounded 15 percent of their own missed free throws.

The other team had the ball, the game was tight, and you wanted to minimize the expected number of points your opponent would earn on this particular possession. How low did the ball-handler’s free throw shooting percentage need to be for you to instruct your team to foul that player (when they were not in the act of shooting)?

Solver Marissa James approached this problem by assuming the probability the ball-handler would make a free throw was F and then broke down the free-throw shooting into a few different cases:

• They missed their first shot, after which your team got the rebound, resulting in 0 points. The probability of this was (1−F)·0.85.
• They missed their first shot, after which their team got the rebound, resulting in 1 point on average. The probability of this was (1−F)·0.15.
• They made their first shot but missed the second, after which your team got the rebound. This resulted in 1 point, and the probability was F·(1−F)·0.85.
• They made their first shot but missed the second, after which their team got the rebound. This resulted in 2 points on average, and the probability was F·(1−F)·0.15.
• They made both of their shots, resulting in 2 points. The probability of this was F².

Multiplying the probability by the number of points for each case and then adding up all five products gave you the average number of points the opposing team would score upon fouling them. This sum turned out to be 0.85F²+F+0.15.

Had you not fouled, your opponent would earn an average of 1 point for their possession. That meant you were better off fouling when 0.85F²+F+0.15 was less than 1, and it was a wash when the quadratic equation 0.85F²+F−0.85 = 0 was true.

Solving the equation, you found that you should have intentionally fouled when the ball-handler’s free-throw shooting percentage was less than 57.2 percent.

So if that ball-handler happened to be, say, Joe Pleasant of the Abilene Christian Wildcats, whose free-throw shooting percentage this year dipped below 60 percent, it might have been tempting to intentionally foul. But you probably shouldn’t have.

Solution to last week’s Riddler Classic

Congratulations to 👏Jared Schmitthenner 👏 of Madison, Wisconsin, winner of last week’s Riddler Classic.

Last week, the rules for men’s basketball in the Riddler Collegiate Athletic Association’s (RCAA) were a little different from those in the NCAA. In the NCAA, when a player is fouled attempting a 3-point shot and misses, they always get three free throw attempts, regardless of how many fouls the opposing team has committed.

But in the RCAA, a player had to earn each additional foul shot by making the previous one (similar to the “bonus” rules of the NCAA mentioned in last week’s Express). In other words, a player could take a second shot if they made the first, and they could take a third shot if they made the second.

Suppose a player on your team had a known shooting profile: Their probability of making the first free throw was p, their probability of making the second was q, and their probability of making the third was r, such that no two of these probabilities were equal. Meanwhile, their expected number of points made for any given 3-point foul (which could be computed from p, q and r) was also known.

What was the greatest number of distinct shooting profiles that were made up of these three different probabilities — p, q and r, in some order for the three shots — that could result in the same overall expected number of points?

For starters, you had to compute the expected number of points given the values of p, q and r. The expected number of points for the first shot was (straightforwardly) just p. As for the second shot, the wording of the problem was slightly ambiguous. A clearer, more complete statement would have been: “Their probability of making the second shot, conditional upon making the first, was q.” Anyway, most readers understood what this meant: The expected number of points for the second shot was pq. Similarly, the expected number of points for the third shot was pqr.

Putting this all together, the expected number of points, which we can call f(p,q,r), was p+pq+pqr. You were then asked how many ways you could permute the distinct values p, q and r inside the function f without changing its value.

For example, what would have happened if the probability of making the first shot had been q, while the second shot had been p? The expected number of points would then have been f(q,p,r), or q+qp+qpr. If this swap didn’t change the number of points, then p+pq+pqr = q+qp+qpr, which meant p had to equal q. In other words, they were only equal when the probabilities of the first two shots were equal. But the problem said all three probabilities had to be distinct!

Working through the remaining permutations, you found it was possible for f(p,q,r) to equal f(p,r,q) as long as p was zero, giving you at most two equivalent profiles.

Alternatively, as solver Dean Ballard showed, you could have had f(p,q,r) equal to f(r,p,q) or f(q,r,p), again giving you at most two equivalent profiles. But then you had to check whether all three of these permutations could be equal at the same time. That is, was it possible to have distinct p, q and r such that p+pq+pqr = r+rp+rpq = q+qr+qrp, or, more simply, p(1+q) = r(1+p) = q(1+r)?

Alas, this was not possible. The moment you assumed p, q and r were all distinct, you could show that one of these three expressions was greater than another. For example, in the case of p < q < r, p(1+q) had to be less than q(1+r), since p was less than q and (1+q) was less than (1+r).

In the end, that meant that you could have at most two profiles that resulted in the same number of points.

Regardless of how your bracket turned out, I hope you enjoyed this year’s edition of March Mathness!

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 riddlercolumn@gmail.com.