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. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
From Scott O’Neil comes an impossible game of sudoku:
As you sit down to pass the time with a sudoku puzzle, you immediately notice that the grid is oddly sparse — only a handful of numbers are initially filled in. But it gets worse. While there aren’t any numbers that occur more than once in the same row, column, or square (i.e., the grid doesn’t ostensibly break any of the sudoku rules), upon closer inspection, you can see that the puzzle is impossible.
What is the smallest possible sum of the initial numbers in the grid? (Note that multiple instances of the same number count separately. So if your impossible grid happened to consist of eight 4s and two 5s, the sum would be 42.)
Since it was impossible to complete the game of sudoku, you might instead enjoy passing the time with a game of Dungeons & Dragons, courtesy of Emma Knight:
The fifth edition of Dungeons & Dragons introduced a system of “advantage and disadvantage.” When you roll a die “with advantage,” you roll the die twice and keep the higher result. Rolling “with disadvantage” is similar, except you keep the lower result instead. The rules further specify that when a player rolls with both advantage and disadvantage, they cancel out, and the player rolls a single die. Yawn!
There are two other, more mathematically interesting ways that advantage and disadvantage could be combined. First, you could have “advantage of disadvantage,” meaning you roll twice with disadvantage and then keep the higher result. Or, you could have “disadvantage of advantage,” meaning you roll twice with advantage and then keep the lower result. With a fair 20-sided die, which situation produces the highest expected roll: advantage of disadvantage, disadvantage of advantage or rolling a single die?
Extra Credit: Instead of maximizing your expected roll, suppose you need to roll N or better with your 20-sided die. For each value of N, is it better to use advantage of disadvantage, disadvantage of advantage or rolling a single die?
Solution to last week’s Riddler Express
Congratulations to 👏 Matt Zefferman 👏 of Marina, California, winner of last week’s Riddler Express.
Last week, you were drawing tiles from a complete set of dominos, which had 28 total tiles. Each tile had two sides, with zero, one, two, three, four, five or six dots on each side.
Question 1: What was the probability of drawing a “double” from a set of dominos — that is, a tile with the same number on both sides?
Question 2: Now you picked a random tile from the set and uncovered only one side, revealing that it had six dots. What was the probability that this tile was a double, with six on both sides?
The first question was straightforward. Of the 28 total tiles, seven of them are doubles: zero-zero, one-one, two-two, three-three, four-four, five-five and six-six. So the probability of drawing a double was 7/28, or 1/4.
The second question was where this puzzle got tricky. Just about 50 percent of submitters gave an answer of 1/7, while the other 50 percent said the answer was 1/4. What was going on here?
Many reasoned that there were seven tiles that had six dots on a side: six-zero, six-one, six-two, six-three, six-four, six-five and six-six. Among these seven, only one of them was a double — six-six. So, given that you picked a tile with at least one side of six, the probability of that tile being a double was 1/7 … right?
You were told that you “uncovered one side of the tile, revealing that it had six dots.” At this point, the “double” tile, with six dots on both sides, was twice as likely as the others to have been picked. Another way to think about it was to look at all the sides (rather than tiles) with six dots and count how many of their counterpart sides also had six dots. While there were seven tiles with six dots, there were eight sides with six dots. And two of those eight sides — the two on the tile with double sixes — had counterparts that also had six dots. So the probability was not 1/7, but rather 2/8, or 1/4.
As many solvers noticed, the answers to the two questions were indeed the same. But how could that be? Raven Deerwater explained that the fact that you “uncovered one side of the tile, revealing that it had six dots” didn’t actually mean anything in the context of the puzzle. You could alternatively have uncovered that one side to find that it had zero, one, two, three, four or five dots. It made no difference — that side had to have some number of dots, and the chances of that tile being a double were not affected. Like Question 1, the answer to Question 2 was again 1/4.
As you can see, when dominos show up in the Riddler, the math is rarely black-and-white.
Solution to last week’s Riddler Classic
Congratulations to 👏 Jason Shaw 👏 of Topeka, Kansas, and 👏 Allen Gu 👏 of Melbourne, Australia, winners of last week’s Riddler Classic.
Last week, a certain 2-year-old was eating his favorite snack: an apple. But he ate it in a very particular way. When he first received the apple, and every minute thereafter, he rotated the apple to a random position, and then looked down. If there was any skin of the apple left in the spot where he planned to take a bite, then he would indeed take that bite. But if there was no skin there (i.e., he had already taken bites at that spot), he wouldn’t take a bite and would rotate the apple for another minute. Once he had bitten off all the skin of the apple, he was done eating.
Suppose the apple was a sphere with a radius of 4 centimeters, and that each bite of the apple was a circle of the sphere whose radius, as measured along the apple’s curved surface, was 1 centimeter. On average, how many minutes would it take this 2-year-old to eat the apple?
You could immediately find a lower bound for the answer by dividing the total surface area of the apple by the surface area of a single bite — there was no way the toddler could have removed all the skin in fewer bites than that. The surface area of the spherical apple was 4𝜋 times the square of the radius, or 64𝜋 square centimeters. Meanwhile, each bite had an area that was slightly less than 𝜋 centimeters (due to the curvature of the apple’s surface), which meant the toddler had to take at least 64 bites.
But that was just a lower bound, while you were asked to find the average number of bites needed. One common approach was computer simulation. You could place thousands of points across a sphere that represented the apple and then remove “bites” of points in random locations, until no points were left. Here is one such simulation, where 1 million red points were randomly scattered across the surface of a sphere:
As you can see, the first few bites removed a lot of the apple’s skin. But less and less skin was removed with each passing minute, since the toddler would only take a bite in the few locations where skin remained.
Now this particular simulation happened to take 392 minutes to remove all the skin. If you were to run this sort of simulation a few thousand times, then you’d have a pretty good sense of which results were likeliest. And that’s exactly what several solvers did:
- Jason Ash ran 10,000 simulations using 10,000 points on a sphere, and found an average of 550 minutes.
- Hector Pefo ran 10,000 simulations using 250,000 points on a square with periodic boundary conditions, and found an average of 565 minutes.
- Allen Gu ran 1,000 simulations using 500,000 points on a sphere, and found an average of 568 minutes.
While they were all close, none of these answers was quite right: They all underestimated the answer. While all the thousands of points in a simulation may have been “consumed” by the simulated bites, there could have still been tiny spaces between the points just outside of the bites. After all, each simulation was only tracking the points, rather than the actual surface of the sphere. Increasing the number of sampled points would have increased the simulation’s accuracy but required more processing power.
As it turned out, this problem — actually, a whole class of problems, including this one — had been asked before. If you think of the sphere’s surface as a set of points, and each bite as a randomly located subset of those points, the question becomes: On average, how many of these subsets are needed to “cover” the set?
To find this average, you needed the probabilities that different numbers of bites covered the sphere. While deriving these probabilities was beyond the scope of this column, it was done by Moran and Fazekas de St. Groth in 1962. Appropriately enough, the authors noted that “[t]his problem arises in practice in the study of the theory of the manner in which antibodies prevent virus particles from attacking cells.”
Winners Jason Shaw and Allen Gu applied these results, finding an average of about 584 minutes. And, just as we expected, this result was slightly greater than the simulated averages reported by other solvers (again, because the simulations didn’t account for the spaces between the sampled points).
Putting these numbers back in context, this meant it would take the toddler almost 10 hours to eat the apple. Yup, that sounds about right.
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 email@example.com.
CORRECTION (May 18, 2020, 12:16 p.m.): A previous version of this article misstated the names of the authors of a 1962 paper. The authors were Moran and Fazekas de St. Groth.