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.
Riddler Express
From Robert Richman comes some baffling breakfast bewilderment:
To share a cylindrical muffin equally with his two toddlers, Robert makes three vertical cuts in a “Y” pattern, producing three equal pieces.
The next morning, his wife wants in on the fun. But before he can cut the muffin into quarters with an “X” pattern, one of his children suggests using an “A” pattern. If Robert were to produce equal fourths in this manner, what would be the ratio of length of the A’s middle bar to the radius of the muffin?
The solution to this Riddler Express can be found in the following week’s column.
Riddler Classic
From Mark Bradwin comes a fishy puzzle about state names:
Ohio is the only state whose name doesn’t share any letters with the word “mackerel.” It’s strange, but it’s true.
But that isn’t the only pairing of a state and a word you can say that about — it’s not even the only fish! Kentucky has “goldfish” to itself, Montana has “jellyfish” and Delaware has “monkfish,” just to name a few.
What is the longest “mackerel?” That is, what is the longest word that doesn’t share any letters with exactly one state? (If multiple “mackerels” are tied for being the longest, can you find them all?)
Extra credit: Which state has the most “mackerels?” That is, which state has the most words for which it is the only state without any letters in common with those words?
(For both the Riddler and the extra credit, please refer to Friend of the Riddler™ Peter Norvig’s word list.)
The solution to this Riddler Classic can be found in the following week’s column.
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Stephen Bonnett ÑÑâÐ of Brooklyn, New York, winner of last week’s Riddler Express.
Last week, you were passing the time with a sudoku puzzle when you noticed that the grid was oddly sparse — only a handful of numbers were initially filled in. But it got worse. While there weren’t any numbers that occurred more than once in the same row, column or square (i.e., the grid didn’t ostensibly break any of the sudoku rules), upon closer inspection, you could see that the puzzle was impossible.
What was the smallest possible sum of the initial numbers in the grid? (Note that multiple instances of the same number counted separately. So if your impossible grid happened to consist of eight 4s and two 5s, the sum would have been 42.)
Many solvers had the right idea — put some 1s into the grid so that a single cell was also constrained to be a 1, and then swap it out for a 2. Using this approach, here was how Goh Pi Han set up the grid:
Sure enough, this grid didn’t ostensibly break the rules of sudoku — no number appeared more than once in any given row, column or square. But because of the placement of the 1s in the left and right squares, the 1 in the central square had to occur in the middle row. Similarly, because of the 1s in the top and bottom squares, the 1 in the central square had to occur in the middle column.
In other words, the 1 had to be in the middle cell of the middle square — exactly where the 2 was! And so this was indeed an impossible sudoku, with no way to fill out the grid. The smallest possible sum of the initial numbers in the grid was 1+1+1+1+2, or 6.
Meanwhile, some readers interpreted “impossible” to mean that there were multiple ways to fill out the grid, in which case the solution was zero — an empty grid could indeed be filled out many, many ways. I didn’t give credit for this interpretation because it wasn’t very interesting.
Finally, solvers Aron Fredrick and Timothy Svendsen both asked and answered their own extra credit problem: How many impossible sudokus were there whose initial numbers added up to the minimum possible value of six?
First, the 2 could be placed in any of the 81 cells. In the squares that were horizontally aligned with the square containing the 2, there were then 18 ways to place two 1s so that they were in different rows from each other and the 2. Similarly, in the squares that were vertically aligned with the square containing the 2, there were 18 ways to place two more 1s so that they were in different columns from each other and the 2. All in all, that meant there were 81×18×18, or 26,244 such arrangements.
That’s a whole lot of impossibilities to consider.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Danny Burke ÑÑâÐ of Chicago, Illinois, winner of last week’s Riddler Classic.
Last week, you grappled with the system of “advantage and disadvantage” from Dungeons & Dragons. When you rolled a die “with advantage,” you rolled it twice and kept the higher result. Rolling “with disadvantage” was similar, except you kept the lower result instead. The rules further specified that when a player rolled with both advantage and disadvantage, they canceled out, and the player rolled a single die. Yawn!
There were two other, more mathematically interesting ways that advantage and disadvantage could have been combined. First, you could have “advantage of disadvantage,” meaning you rolled twice with disadvantage and then keep the higher result. Or, you could have “disadvantage of advantage,” meaning you rolled twice with advantage and then kept the lower result. With a fair 20-sided die, which situation produced the highest expected roll: advantage of disadvantage, disadvantage of advantage or rolling a single die?
As the puzzle’s submitter, Emma Knight, observed, you didn’t need to work out all the cases. Both advantage of disadvantage and disadvantage of advantage (try saying that 10 times fast!) required a total of four rolls. We can label those four rolls in (nonstrictly) increasing order 1, 2, 3 and 4. At this point, there are three equally likely pairings of these numbers, where each pair represents the two rolls of an advantage or disadvantage: (12)(34), (13)(24) and (14)(23).
For these three scenarios, advantage of disadvantage produced results of 3, 2 and 2, for an average of about 2.33. Meanwhile, disadvantage of advantage produced results of 2, 3 and 3, for an average of about 2.67. Finally, rolling a single die would result in the average of all four numbers, or 2.5. That meant you would have the highest expected roll with disadvantage of advantage.
But for Riddler Nation, this solution was just the beginning.
First, several solvers found the precise expected values for each of the three strategies. Rolling a single die was the most straightforward — there were 20 possible outcomes (1 through 20), each with a probability of 1/20, for an expected value of 10.5. Lily Koffman efficiently summated her way through the 204 possible scenarios, finding that advantage of disadvantage gave an average roll of 9.8333375, while disadvantage of advantage had an average of 11.1666625. As with our simplified approach, disadvantage of advantage came out on top.
For those interested in the distribution of outcomes, computers came in handy. Julian Gerez ran 1 million simulations to measure the expected values with precision. Robert Sturrock ran 100,000 simulations, as did Quoc Tran in obtaining the following graph:
The flat green curve shows the distribution of rolls for a single die, the blue curve shows advantage of disadvantage, and the red curve shows disadvantage of advantage. The red curve was shifted to the right and had the greatest mean of the three distributions, once again confirming our answer.
For the extra credit, you needed to roll N or better with your 20-sided die. For each value of N, was it better to use advantage of disadvantage, disadvantage of advantage or rolling a single die?
To figure this out this, you needed a cumulative distribution function, summing the probabilities across values of N and up. There was a 100 percent chance that advantage of disadvantage, disadvantage of advantage and rolling a single die would all achieve the minimum possible value of 1 or better. But as N increased beyond 1, things got dicey.
Jason Ash found these cumulative distributions by coding, while Laurent Lessard found them analytically. Either way, disadvantage of advantage was the best strategy when 2 ≤ N ≤ 13, but rolling a single die was best when 14 ≤ N ≤ 20.
But what was so special about the numbers 13 and 14? Why did the switch happen there?
Laurent and Allen Gu took the problem a step beyond the extra credit, looking at not 20-sided dice, but k-sided dice. As they increased k to larger and larger values (i.e., in the continuous limit where the dice became random number generators), Laurent and Allen both found that the transition occurred when N was equal to 1 + (√5 − 1)/2·k. When k was 20, the expression was approximately 13.36, which was why the optimal strategy switched between 13 and 14. Also of note — the coefficient of k happened to be the reciprocal of the golden ratio. Neat!
Below is Laurent’s graph for the continuous case. The orange and green curves intersected where disadvantage of advantage gave way to rolling a single die as the optimal strategy for achieving a minimum target score.
Finally, for any readers who are still yawning, thinking even advantage of disadvantage and disadvantage of advantage are too simplistic when it comes to combining effects in Dungeons & Dragons, Benjamin Zev suggested another option, which he dubbed “middlevantage”: Roll three times, and take the middle value. Andrew Heairet answered this challenge, finding that middlevantage was never your best option.
And with that, I hope it’s a long time before I next have to type out the words advantage and disadvantage.
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.