Can You Knock Down The Last Bowling Pin?
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
From Michael Branicky comes a puzzle that was inspired by an email thread from James Propp:
Suppose you roll a fair six-sided die on a ridged gnocchi board, such that two adjacent faces come up every time.
On average, what is the sum of the numbers shown on those two faces?
Riddler Classic
Magritte the bowler is back! This time, he is competing head-to-head against fellow bowler Fosse. However, rather than knocking down 10 pins arranged in a triangular formation, they are trying to knock down N2 pins (where N is some very, very large number) arranged in a rhombus, as shown below:
When Magritte rolls, he always knocks down the topmost pin. Then, if any pin gets knocked down, it has a 50 percent chance of knocking down either of the two pins directly behind it, independently of each other. (If there is only one pin directly behind it, then it too has a 50 percent chance of being knocked over.)
Fosse is a stronger bowler than Magritte. Like Magritte, she always knocks down the topmost pin. But each pin that’s knocked down then has a 70 percent chance (rather than Magritte’s 50 percent) of knocking down any of the pins directly behind it.
What are Magritte’s and Fosse’s respective probabilities of knocking down the bottommost pin in the rhombus formation?
Solution to last week’s Riddler Express
Congratulations to 👏 Vishal Nayak 👏 of Canton, Michigan, winner of last week’s Riddler Express.
Last week, you played a version of the shell game. In each game, a woman placed a ball under one of three cups and then swapped the positions of pairs of cups several times before asking passersby which cup they thought the ball was now under.
You had it on good authority that she was playing fairly, performing all the moves in plain sight, albeit too fast for you to track precisely which cups she was moving. However, you did have one additional key piece of information — every time she swapped cups, one of them had the ball. In other words, she never swapped the two empty cups.
When it was your turn to guess, you noted which cup she initially placed the ball under. Then, as she began to swap cups, you closed your eyes and counted the number of swaps. Once she was done, you opened your eyes again. What was your best strategy for guessing which cup had the ball?
For starters, let’s assume that, with each move, the woman was randomly choosing which empty cup to swap with the cup that had the ball under it. (We’ll return to this assumption later.)
After zero swaps, you know the ball is definitely under the cup where it was placed, which we’ll call cup A. After one swap, it was definitely under one of the other two cups, which we’ll call cups B and C. Now after two swaps, there was a 50 percent chance that the ball was returned to cup A (from either B or C), but also a 50 percent chance that the ball switched between B and C. At this point, the ball had a 50 percent chance of being in A, a 25 percent chance of being in B and a 25 percent chance of being in C. That meant your best bet was to guess cup A.
With each swap, the probability continued to swing back and forth, alternating between slightly favoring cup A, slightly favoring both cups B and C, then back to slightly favoring cup A again. Using Markov Chains, solver Tom Singer was able to compute the exact probabilities for each cup as a function of the number of swaps N. The probability the ball was in cup A was 1/3 + 2/3·(−1/2)N, while the probabilities the ball was in cups B or C were both 1/3 − 1/3·(−1/2)N.
So if the woman was randomly picking empty cups with which to swap, then your best bet was to pick the cup under which the ball was initially placed after an even number of swaps, and either of the two remaining cups after an odd number of swaps.
Now, what if the woman had not been randomly choosing cups with which to swap the cup with the ball? In this case, she certainly could have messed with your head. For example, suppose she had swapped cups A and B, then cups B and C, then cups A and C. If she randomly picked an empty cup thereafter, then your optimal strategy for the random case (picking cup A when the number of swaps was even) would have been the worst possible strategy. Alternatively, she could have initially swapped cups A with either B or C, and then swapped B or C with A again with a probability of 1/6. Beyond that point, all three cups would have been equally likely to contain the ball.
For the record, I accepted solutions that assumed either random swapping or more nefarious swapping.
Solution to last week’s Riddler Classic
Congratulations to 👏 Izumihara Ryoma 👏 of Toyooka, Japan, winner of last week’s Riddler Classic.
Last week, you played a quantum shell game. Instead of a ball, you were trying to capture an electron. Now, you weren’t sure precisely where it was, but you knew it was somewhere on a two-dimensional surface. What’s more, you knew the probability distribution was a 2D Gaussian (or “normal”) distribution. More precisely, the probability the electron was a distance r units in any direction from some central point was proportional to exp(−r2/2).
You had four cylindrical cups, each of which had a radius of 1 unit. In this game, you wanted to place the cups over the surface to maximize the probability that the electron was in one of the cups.
How should you have placed the cups, and what was the probability you caught the electron?
First off, what was the electron’s actual probability distribution? To figure that out, you needed to normalize it (i.e., ensure the total volume under the probability distribution was 1). That meant the probability the election was a distance r from the central point was exp(−r2/2)/(2𝜋).
From this point onward, there was a lot of calculus. To find the probability the electron was in a cup whose center was a distance d from the central point, you had to integrate the probability density within the cup. And to find the distance between the central point and each point in the cup (parameterized by a distance 𝜌 from the cup’s center and an angle 𝜙 from the vector to the central point), you needed the law of cosines. Solver Steve Curry illustrated this integral below:
From there, you had to evaluate this integral four times — one for each cup, which was a corresponding distance d from the central point. When d was closer to zero, that meant the cup was closer to the maximum of the probability distribution and was therefore more likely to contain the electron. However, the catch was that none of the cups could overlap, so having one of them closer to the central point meant pushing the other three cups away (in two dimensions). And so this puzzle was something of a cross between an optimization problem and a close-packing problem.
You might have been tempted to place one cup directly over the central point. This cup alone had almost a 40 percent chance of containing the electron. But that also meant the centers of the remaining three cups all had to be at least a distance 2 from the central point. With all four cups together, you only had a 64 percent chance of catching the electron.
Next, some solvers tried a symmetric, square arrangement of cups, surrounding the central point. In this arrangement, each cup’s center was a distance √2 from the central point. This gave you a 72.3 percent chance of catching the electron.
It turned out that the best arrangement was to have the four cups form a close-packed rhombus, centered on the central point of the probability distribution. This gave you a 77.8 percent chance of catching the electron. Solver Jenny Mitchell graphed the cups and a contour map of the probability distribution within them:
Even though there were gaps between the cups on either side of the central point, this turned out to be the best you could do.
In this puzzle, it so happened that the radii of the cups equaled the characteristic radius of the 2D Gaussian. But what if the cups had been larger or smaller? While you weren’t asked to figure this out, I found this to be a rather fascinating extension of the problem.
The graph below shows how the probability of catching the electron varied with cup radius for the three aforementioned arrangements (one cup directly over the center, the square arrangement and the rhombus arrangement). When the cups were smaller — including when the cup radius was 1 (i.e., it equaled the characteristic radius) — the rhombus formation was the best. But as the cups got larger, having one central cup became the better formation. (What’s more, the rhombus formation appeared to show a rather interesting non-monotonic behavior with a local minimum when the radius was about 2.685.)
For extra credit, you tried to catch the electron with different numbers of cups, like three, five or six cups. Jenny solved these cases as well, demonstrating how the probability increased with each additional cup:
According to Jenny, as the number of cups went to infinity, the probability of catching the electron asymptotically approached about 90.7 percent.
(If only you had quantum cups that could be superimposed. Then you could have driven this probability even closer to 100 percent.)
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.
