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
From Steve Simon, an adorable living-room puzzle:
Your baby is learning to walk. The baby begins by holding onto a couch. Whenever she is next to the couch, there is a 25 percent chance that she will take a step forward and a 75 percent chance that she will stay clutching the couch. If the baby is one or more steps away from the couch, there’s a 25 percent chance that she will take a step forward, a 25 percent chance she’ll stay in place and a 50 percent chance she’ll take one step back toward the couch.
In the long run, what percent of the time does the baby choose to clutch the couch?
Riddler Classic
From Corey Fisher, a deadly Tolkienesque problem:
A giant troll captures 10 dwarves and locks them up in his cave. That night, he tells them that in the morning he will decide their fate according to the following rules:
- The 10 dwarves will be lined up from shortest to tallest so each dwarf can see all the shorter dwarves in front of him, but cannot see the taller dwarves behind him.
- A white or black dot will be randomly put on top of each dwarf’s head so that no dwarf can see his own dot but they can all see the tops of the heads of all the shorter dwarves.
- Starting with the tallest, each dwarf will be asked the color of his dot.
- If the dwarf answers incorrectly, the troll will kill the dwarf.
- If the dwarf answers correctly, he will be magically, instantly transported to his home far away.
- Each dwarf present can hear the previous answers, but cannot hear whether a dwarf is killed or magically freed.
The dwarves have the night to plan how best to answer. What strategy should be used so the fewest dwarves die, and what is the maximum number of dwarves that can be saved with this strategy?
Extra credit: What if there are only five dwarves?
Solution to last week’s Riddler Express
Congratulations to 👏 Jack Millson 👏 of Allston, Massachusetts, winner of last week’s Express puzzle!
You, the most eligible bachelorette in the kingdom, have decided to marry a prince. The king has invited you to his castle to meet his three sons. The eldest prince is honest and always tells the truth. The youngest prince is dishonest and always lies. And the middle prince is mischievous and tells the truth sometimes and lies the rest of the time. You want to marry either the eldest or the youngest, because at least you’ll know where you stand with them. You can’t tell them apart by looking, but the king grants you a single yes-or-no question that you may direct to exactly one of the brothers. What one question can you ask that ensures you do not marry the middle prince?
The puzzle’s submitter, Chris Horgan, has one strategy that will do the trick. Suppose you call the princes Al, Bob and Chuck. Ask Al the following: “If I asked you if Bob was the middle brother, would you say yes?” If he says yes, marry Chuck and you’re guaranteed to avoid the mischievous brother. If Al says no, though, marry Bob. (Poor Al.)
Why does asking a hypothetical question work better than asking the question outright? Let’s break down all the possible true identities of Al, Bob and Chuck, how they’d each answer and what husband you’d choose to marry in all situations. There are six cases to consider.
| AL | BOB | CHUCK | IS BOB THE MIDDLE BROTHER? | AL’S RESPONSE | YOUR RESULTING HUSBAND IS… |
|---|---|---|---|---|---|
| Honest | Mischievous | Dishonest | Yes | Yes | Dishonest |
| Honest | Dishonest | Mischievous | No | No | Dishonest |
| Mischievous | Honest | Dishonest | No | Yes or no | Honest or dishonest |
| Mischievous | Dishonest | Honest | No | Yes or no | Honest or dishonest |
| Dishonest | Honest | Mischievous | No | No | Honest |
| Dishonest | Mischievous | Honest | Yes | Yes | Honest |
In every case, you marry either the honest or dishonest prince, and you successfully avoid the mischievous one! That’s because by asking a question about how the prince would answer a different, hypothetical question, we coerce the honest and dishonest princes into answering the same way, allowing us in both cases to avoid a life wedded to the mischief-maker.
Presuppose Bob really is the middle brother. When you ask the honest brother how he would respond if you asked whether Bob was the middle brother, the honest brother will respond yes, he would say Bob is the middle brother, since Bob really is the middle brother. The dishonest brother would also say yes, because he always has to lie. What he’s really saying is: “Yes, I’d tell you Bob is the middle brother, because when you actually asked me the question, I’d tell you Bob wasn’t the middle brother, because I have to lie!” In other words, he’s lying about whether he’d lie to you.
Another key is to ask a question of a person that you will never marry, because the brother to whom you pose the question may well be the mischievous one.
Solution to last week’s Riddler Classic
Congratulations to 👏 Matthew Monaghan 👏 of Lincoln, Nebraska, winner of last week’s Classic puzzle!
Four families live on four square ranches, arranged in a two-by-two grid. They each build a small house independently and at random somewhere on their ranches, and, as the neighbors become acquainted, they connect the four houses with a circuit of four paths, which form a quadrilateral. The area bounded by that quadrilateral also happens to be the area in which the families’ children are allowed to roam. What is the probability that the children are able to travel in a straight line from any allowed place to any other allowed place? In other words, what is the probability that the quadrilateral is convex?
The probability is about 91 percent. The ranchers’ children are quite likely to be able to travel in whatever straight lines they please within their allowed area.
Most solvers took a computational, simulation-based approach, randomly building thousands and thousands of houses on thousands and thousands of ranches and checking the convexity of the quadrilaterals they formed. Robbie Ostrow and Jordan McQueen concocted nifty animations of their simulations and were kind enough to include their code. Tyler Barron turned his solution into a video, which is sure to go viral:
But there is also a precise, analytical answer: \(11/6 – 4\cdot \ln(2)/3 \approx 0.909137\). It can be calculated with a bit of geometry, probability, algebra and integration.
Let’s begin with this very helpful diagram created by Laurent Lessard, along with his excellent solution, adapted below. Each ranch is represented mathematically on a grid as a 1-unit-by-1-unit square, and the origin (0, 0) is placed at the center of the four ranches.
The blue points — J, K, L and M — are hypothetical houses built by the ranching families. For any given arrangement of the houses, at most one house can be the “troublemaker” that makes the quadrilateral non-convex. The probability that that house is K, for example, is the probability that K falls in the shaded triangle in the diagram above. If it fell in that triangle, the children wouldn’t be able to walk in a straight line from house J to house L, for example, without leaving their allowed area.
So what is the probability that K falls in that triangle? It’s simply the area of the triangle, because the area of the ranch itself is 1. The area of that triangle is one-half its base times its height (½ \(xy\)) and the expectation of that area depends on the randomly chosen locations of the neighbors’ houses J and L. All that’s left now is a bit of careful algebra and calculus.
The expected area of the triangle is obtained by integrating over all the possible randomly chosen coordinates of the two neighboring houses. (As Lessard explains, for some locations of J and L, \(x\) and \(y\) will be negative, and we can account for that by multiplying our formula by ½.)
\begin{equation}\int_0^1 \int_0^1 \int_0^1 \int_0^1 \frac{1}{2}\frac{1}{2}xy~da~db~dp~dq\end{equation}
Before we can calculate this, we need to know x and y in terms of a, b, p and q. Knowing the slope-intercept equation for a line, we do a bit of algebra and arrive at \(x = \frac{bp-aq}{b+q}\) and \(y = \frac{bp-aq}{a+p}\), which we can plug into our integral above. And the other three vertices could also cause the problem, so we must multiply our probability by 4. Finally, since we’re interested in the probability that the quadrilateral is convex, we subtract all this from 1. That gives us an expression for our final answer. (This is tricky to solve by hand! But an online calculator can do it for us.)
\begin{equation}1 – \int_0^1 \int_0^1 \int_0^1 \int_0^1 \frac{(bp-aq)^2}{(b+q)(a+p)}~da~db~dp~dq \approx 0.909137\end{equation}
Chris Kucharczyk extended the problem to outer space, where it takes on a third dimension. Chris found that, for these space ranchers’ children, the probability dropped to about 68 percent. He illustrated some cosmic cases, shown below.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.