Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-sized and 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 if you have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
Adapted from the work of puzzle legend Henry Dudeney, a squaring-the-square puzzle:
You are handed a piece of paper containing the 13-by-13 square shown below, and you must divide it into some smaller square pieces. If you are only allowed to cut along the lines, what is the smallest number of squares you can divide this larger square into? (You could, for example, divide it into one 12-by-12 square and 25 one-by-one squares for a total of 26 squares, but you can do much better.)
Riddler Classic
The Kentucky Derby is on Saturday, and a field of 20 horses is slated to run “the fastest two minutes in sports” in pursuit of the right to be draped with a blanket of roses. But let’s consider, instead, the Lucky Derby, where things are a little more bizarre:
The bugle sounds, and 20 horses make their way to the starting gate for the first annual Lucky Derby. These horses, all trained at the mysterious Riddler Stables, are special. Each second, every Riddler-trained horse takes one step. Each step is exactly one meter long. But what these horses exhibit in precision, they lack in sense of direction. Most of the time, their steps are forward (toward the finish line) but the rest of the time they are backward (away from the finish line). As an avid fan of the Lucky Derby, you’ve done exhaustive research on these 20 competitors. You know that Horse One goes forward 52 percent of the time, Horse Two 54 percent of the time, Horse Three 56 percent, and so on, up to the favorite filly, Horse Twenty, who steps forward 90 percent of the time. The horses’ steps are taken independently of one another, and the finish line is 200 meters from the starting gate.
Handicap this race and place your bets! In other words, what are the odds (a percentage is fine) that each horse wins?
Extra credit: Animate this derby. I’ll broadcast the highlights next week.
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Martin Williams ÑÑâÐ of Markham, Ontario, winner of last week’s Express puzzle!
Three smart logicians are standing in a line, so that they can only see the logicians in front of them. A hat salesman comes along and shows the three logicians that he has three white hats and two black hats. He places one hat on each logician’s head and hides the remaining hats. He then says to the logicians, “Can anyone tell me what color hat is on her own head?” No one responds. He repeats, “Can anyone tell me what color hat is on her own head?” Still no answer. A third time: “Can anyone tell me what color hat is on her own head?” One of the logicians speaks up and gives the correct answer. Who spoke, and what color hat is on her head?
Name the logicians One, Two and Three. Logician One is at the back of the line and can see the hats of Two and Three. Logician Two is in the middle and can only see the hat of Three. Logician Three can’t see any hats.
There are eight arrangements of white and black hats we can consider. (Each logician could have a black or a white hat, and two times two times two is eight.) We can eliminate one of them right away: The salesman only has two black hats, so everyone knows that not everyone can be wearing a black hat. So we’re left with seven possibilities for the hats of One, Two and Three, respectively: WWW, WWB, WBW, BWW, WBB, BWB and BBW.
When none of them know the color of their hat when first asked, we can eliminate WBB. If One had seen two black hats in front of her, she’d have known that her own hat was white for sure. This leaves WWW, WWB, WBW, BWW, BWB and BBW. Two and Three now know that they aren’t both wearing black hats.
When none of them knows the color of her own hat when asked a second time, we can eliminate WWB and BWB. If Two sees Three wearing a black hat, Two knows that her hat must be white for sure. This leaves WWW, WBW, BWW and BBW.
In all of these cases, Three’s hat is white! So logician Three, despite not being able to see any hats, speaks up and declares — correctly — that her hat is white.
Scott Anthony, in perhaps my favorite Riddler solution of all time, submitted his answer exclusively in the form of emoji:
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Benjamin Phillabaum ÑÑâÐ of Chicago, winner of last week’s Classic puzzle!
You play a game with four balls: One ball is red, one is blue, one is green and one is yellow. They are placed in a box. You draw a ball out of the box at random and note its color. Without replacing the first ball, you draw a second ball and then paint it to match the color of the first. Replace both balls and repeat the process. The game ends when all four balls have become the same color. What is the expected number of turns to finish the game?
It takes nine turns on average.
As Chris Swindell explained in his elegant solution, at any point in the game, there are five possibilities for the balls’ colors when they’re sitting unseen in the box: ABCD, AABC, AABB, AAAB and AAAA. (We don’t care what specific colors the balls are, we only care that they all to wind up the same color. “A” could mean blue or red or green or yellow, depending on what happens as we play the game. All that matters is which balls match and which don’t.) We might draw a ball of the “A” color and paint a ball of the “B” color to match, or we might draw a ball of the “C” color and paint a ball of the “A” color to match, and so on. Our box begins, for example, with each of the balls painted a different color — ABCD. After the first turn, regardless of what we draw and paint, they’ll become AABC.
But how do we capture this problem mathematically? One option is to set up a system of equations. Let a variable represent the expected number of turns to get from that specific pattern of ball colors to our desired state, where all the balls are the same color. For example, if the box has an AAAB assortment of ball colors and we take one turn, there is a one-half chance we’ll wind up where we started, with colors AAAB, and a one-fourth chance we’ll paint an “A” ball the “B” color, winding up with AABB. We can represent that like so:
\begin{equation}AAAB = 1 + (1/2) \cdot AAAB + (1/4) \cdot AABB\end{equation}
If our balls’ colors are AABB and we take one turn, there is a one-third chance the colors will remain AABB and a two-thirds chance they’ll wind up AAAB, which we can represent like this:
\begin{equation}AABB = 1 + (1/3) \cdot AABB + (2/3) \cdot AAAB\end{equation}
We can do this for the other two possibilities as well:
\begin{equation}AABC = 1 + (1/2) \cdot AABC + (1/6) \cdot AABB + (1/3) \cdot AAAB\end{equation}
\begin{equation}ABCD = 1 + AABC\end{equation}
All we do now is solve this system for the state at the beginning of the game, ABCD, using basic algebra or, as my calculus teacher used to say, plugging and chugging. That gives us ABCD = 9.
Victor Bible calculated the distribution of the number of turns the game could take:
William Tressler crafted an excellent animated simulation of the game, while Sawyer Tabony shared his lower-tech work:
Laurent Lessard and Tim Black also provided lucid explanations of the math behind this puzzle, using a different approach relying on a Markov transition matrix. And Taylor Malone walked us through his programmatic solution.
More generally, for N balls painted N different colors, the game takes on average \((N-1)^2\) turns to complete.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.
CORRECTION (May 5, 10:40 a.m.): An earlier version of this week’s Riddler Classic problem included some impossible math. We originally said that in a 20-horse field, Horse One steps forward 50 percent of the time, and each subsequent horse is 2 percentage points more likely to step forward, up to Horse Twenty, which steps forward 90 percent of the time. That would require 21 horses, not 20. So we’ve adjusted the rules so that Horse One moves forward 52 percent of the time, Horse Two 54, and so on. Horse 20 still moves forward 90 percent of the time.