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
A sunny al fresco puzzle:
On a lovely spring day, you and I agree to meet for a lunch picnic at the fountain in the center of our favorite park. We agree that we’ll each arrive sometime from noon and 1 p.m., and that whoever arrives first will wait up to 15 minutes for the other. If the other person doesn’t show by then, the first person will abandon the plans and spend the day with a more punctual friend. If we both arrive at the fountain at an independently random time between noon and 1, what are the chances our picnic actually happens?
Riddler Classic
The U.S. Chess Championships began this week in St. Louis. (Stay tuned for FiveThirtyEight coverage!) Let’s get in the spirit with a few chess problems:
On a standard chessboard, what is the largest number of each piece (work it out first for kings only, then for knights only, bishops, rooks and queens) that can be placed on the board so that none of the pieces attack each other? (You don’t have to do pawns!)
What is the smallest number of each piece that can be placed on the board such that every empty square is under attack?
Extra credit: For each question above, how many possible correct arrangements are there?
Solution to last week’s Riddler Express
Congratulations to 👏 John McCulloch 👏 of Los Angeles, winner of last week’s Express puzzle!
Your baby is learning to walk. She begins standing, holding onto the couch. There’s a 25 percent chance she’ll take a step forward, and a 75 percent chance she’ll stay put, clutching the couch. If she’s ever a step or more away from the couch, there’s a 25 percent chance she’ll take another step forward, a 25 percent chance she’ll stay where she is, and a 50 percent chance she’ll take a step back, toward the couch. In the long run, what percentage of the time does the baby clutch the couch?
She’ll clutch the couch 50 percent of the time. Let’s set up a system of equations based on what we know about the baby’s behavior, adapted from the elegant solution submitted by Al Vyssotsky. Let a be the long-run probability that the baby is clutching the couch. Let b be the probability she is one step away, c be the probability she’s two steps away, and so on. The baby can reach “state a” from either state a (staying put at the couch) or from state b (by taking a step backward). So we can define a as \(a = 0.75a + 0.5b\). Simplifying that gives \(a=2b\). The baby can reach state b from state a (taking a step forward), state b (staying put) or state c (taking a step backward). So we can define b as \(b = 0.25a + 0.25b +0.5c\). Simplifying that gives \(b=2c\). We can keep going: \(c=2d\), \(d=2e\), \(e=2f\), and so on. Since the baby is always going to be somewhere, we know all these probabilities have to add up to 1. Or, to put it another way:
\begin{equation}1= a+b+c+d+\ldots\end{equation}
So, given what we’ve solved for already, we know
\begin{equation}1 = a + a/2 + a/4 + a/8 +\ldots\end{equation}
The right-hand side is a well-known geometric series which converges, since its terms are getting smaller and smaller sufficiently quickly, to \(2a\). Therefore \(a = 1/2\).
Many other solvers took a computational approach, and you can see more detail in the coded examples provided by Samuel Scherl and Justin Brookman. Tim Bedeaux illustrated, via simulation of many babies, how the percentage of babies clutching the couch converges to 50 percent as the baby takes its steps.
Solution to last week’s Riddler Classic
Congratulations to 👏 Anders Skjäl 👏 of Åbo, Finland, winner of last week’s Classic puzzle!
A giant troll captures 10 dwarves and locks them up in his cave. The following morning, he will decide their fate through a series of rules. The troll will randomly place a white or black dot on each dwarf’s head. He’ll then line them up single file, shortest to tallest, so that each dwarf can see all the shorter dwarves in front of him — and their dots — but none of the taller dwarves behind him. Starting with the tallest, each dwarf will be asked the color of his dot. If he gets the color wrong, the troll kills him. If he gets it right, he’s magically and instantly transported to safety. Each dwarf can hear the answers of the others, but does not know whether they are killed or saved. The dwarves have the night to hatch a plan. What strategy can they use so that the fewest dwarves die, and how many dwarves can be saved?
Nine of the 10 dwarves can be saved for sure and, with a little luck, all 10 will escape the troll’s clutches. How? The dwarves agree on the following plan: The first, tallest dwarf will risk life and limb to save the others. Since he has no information to go on to determine his own dot’s color, he can use his guess to inform the others. The dwarves agree that if the number of white dots the tallest dwarf sees is even, he should say “white,” and if it’s odd, he should say “black.”
That first dwarf only has a 50-50 chance of survival, but all of his compatriots will now survive for sure because they know why he said the color he said. Suppose the first dwarf says “white,” meaning he sees an even number of white dots. Then it’s the second dwarf’s turn. If he also sees an even number of white dots, then he knows for sure that his dot is black. If, instead, he sees an odd number of white dots, then he knows for sure that his dot is white. Based on the responses of the first two dwarves, the third can then also determine the “evenness” or “oddness” of the remaining white dots. If what he sees matches that, his must be black, if not, white, and so on.
Regardless of how many dwarves there are (say there are N), at least N-1 can be saved for sure, and all N can be saved half the time! Your fellow dwarves thank you, tallest dwarf.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.