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 Andrew Heairet comes a puzzle that is sure to whet your appetite:
You and a friend are grilling two small square burger patties whose sides are 5 centimeters long. However, you only have one slice of cheese remaining, which is also square and whose sides are 7 centimeters long. You want to cut the slice so that all of the cheese is evenly split between the two patties, and no cheese is spilling over either patty and onto the grill.
What is the smallest number of cuts you need to make? You can only make straight cuts, and you should assume that the cheese is stationary during the cutting process.
Riddler Classic
The Monty Hall problem is a classic case of conditional probability. In the original problem, there are three doors, two of which have goats behind them, while the third has a prize. You pick one of the doors, and then Monty (who knows in advance which door has the prize) will always open another door, revealing a goat behind it. It’s then up to you to choose whether to stay with your initial guess or to switch to the remaining door. Your best bet is to switch doors, in which case you will win the prize two-thirds of the time.
Now suppose Monty changes the rules. First, he will randomly pick a number of goats to put behind the doors: zero, one, two or three, each with a 25 percent chance. After the number of goats is chosen, they are assigned to the doors at random, and each door has at most one goat. Any doors that don’t have a goat behind them have an identical prize behind them.
At this point, you choose a door. If Monty is able to open another door, revealing a goat, he will do so. But if no other doors have goats behind them, he will tell you that is the case.
It just so happens that when you play, Monty is able to open another door, revealing a goat behind it. Should you stay with your original selection or switch? And what are your chances of winning the prize?
Solution to last week’s Riddler Express
Congratulations to 👏 James Goodman 👏 of Göttingen, Germany, winner of last week’s Riddler Express.
Last week, you were asked to solve a royal murder mystery:
You were told that the white knight that took the black queen had moved exactly eight times. How was this possible?
At first glance, it appeared that the white knight in question originated from the lower left corner of the board. However, there just didn’t seem to be a way for the knight to have reached the black queen in exactly eight moves.
Indeed, with a key insight, you could prove this impossibility. As solver Jeevaka Dassanayake observed, every time a knight moves, it either goes from a white square to a black square or a black square back to a white square. So because this knight started on a white square, then after any even number of moves — yes, that means after eight moves — it must again be on a white square. However, the black queen was on a black square. So there was no way the white knight from the lower left could have killed the black queen in eight moves.
In submitting this puzzle, Yan Zhang pointed to a particular saying of Sherlock Holmes: “When you have eliminated the impossible, whatever remains, however improbable, must be the truth.” If the white knight that took the queen wasn’t the one from the lower left, it must have been the one from the lower right.
Sure enough, the white knight in the lower right started on a black square, meaning it could take the black queen in an even number of moves. But what about the knight that’s currently occupying that black square in the lower right? Well, that was our old friend — the knight that started in the bottom left — and it got there in an odd number of moves.
In the end, there were many sequences of moves that met the criteria stated in the puzzle. Here is one such sequence, courtesy of Andrew Heairet (the submitter of this week’s Express):
Lucas Yan, meanwhile, reverse-engineered the game in Python, finding another sequence of moves.
If this chess strategy didn’t have a name before, it does now — solver ♔ Oliver Roeder ♔, my predecessor here at FiveThirtyEight, named it the “Drunken Dressage Defense,” possibly due to all that horsing around.
Finally, for those of you who are interested in more retrograde analysis of chess games, I recommend the works of Raymond Smullyan.
Solution to last week’s Riddler Classic
Congratulations to 👏 Matthew Cowen-Green 👏 of New York, winner of last week’s Riddler Classic.
Last week, you looked at a version of Conway’s Game of Life on a square grid with three rows, N columns and periodic boundary conditions — that is, squares in the first row (or column) were considered to be neighbors with squares in the last row (or column).
Each square was also either alive or dead and had eight neighbors — the eight squares that surrounded it. After every step in time, or “tick,” all the cells were simultaneously updated according to the following rules:
- A living square with two or three living neighbors remained living.
- A living square with any other number of living neighbors died (due to under- or overpopulation).
- A dead square with exactly three living neighbors came alive (due to reproduction).
In the Game of Life, some formations of living squares are known as “oscillators,” which change form from one tick to the next, ultimately returning back to their original formation. What was the smallest value of N, the number of columns, that could support an oscillator?
Some solvers thought to check the simplest oscillator from the standard Game of Life, known as a “blinker,” which consists of three squares that alternate between horizontal and vertical arrangements. However, when the three squares were vertically aligned, the topmost square was neighbors with the bottommost square due to the periodic boundary conditions. This meant your everyday blinker simply couldn’t exist on our modified grid, and you had to hunt for more complicated oscillators.
The smallest value of N that supported an oscillator turned out to be four, and it had a period of two (i.e., it returned to its original arrangement every two ticks). For this oscillator, two adjacent columns would be alive on one tick, the other two columns would be alive on the next tick, and then the original two columns would be alive again. Here’s an animation of this solution, courtesy of Michael Branicky:
But the fun didn’t stop there. When hunting for oscillators, if you treated the three squares in a column as a single unit that were either all alive or dead together, a new set of rules emerged:
- A living column with no neighboring living columns remained living.
- A living column with one or two neighboring living columns died (due to overpopulation).
- A dead column with exactly one neighboring living column came alive (due to reproduction).
So what was once a 3 by N grid of squares was now effectively a 1 by N grid of columns, which made the analysis slightly more manageable. It also meant that this game behaved like one of Stephen Wolfram’s cellular automata rules — rule 22 to be precise.
With this in mind, several solvers discovered all sorts of larger oscillators. Michael found that after N = 4, the next smallest value of N that could support an oscillator was N = 7. Nine-year-old (!) Natesh Larkin found a period-4 oscillator when N = 9:
Allen Gu found a period-384 oscillator when N = 24. And Josh Silverman found a period-1215 oscillator when N = 27:
Finally, if you’d like to play around some more yourself, check out the applet Gabe Pezanoski-Cohen made, which lets you search for oscillators on grids of varying sizes with periodic boundary conditions.
Oh, and if anyone has figured out the general pattern of what periods are possible for a given value of N, do share!
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.