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-size 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 have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
From Max Rosmarin, a puzzle of villainous improv:
Imagine a group of five improvisers performing the following acting exercise: They all begin a scene together, establishing a character for themselves. Halfway through the scene, each improviser switches to a character someone else has been playing, such that the same five characters remain for the entire scene but no one plays the same character in both halves. As it happens, two of the characters in the scene are villains, and three are heroes.
Assuming that every valid reallocation of characters is equally likely, what is the probability that at least one of the actors plays a villain in both halves of the scene?
Riddler Classic
From Ben Gundry via Eric Emmet, find and replace with a twist:
Riddler Nation has been enlisted by the Pentagon to perform crucial (and arithmetical) intelligence gathering. Our mission: decode two equations. In each of them, every different letter stands for a different digit. But there is a minor problem in both equations.
In the first equation, letters accidentally were smudged on their clandestine journey to a safe room within Riddler Headquarters and are now unreadable. (These are represented with dashes below.) But we know that all 10 digits, 0 through 9, appear in the equation.
What digits belong to what letters, and what are the dashes?
In the second equation, our mathematical spies have said that one of the letters in the equation is wrong. But they can’t remember which one. Which is it?
Solution to last week’s Riddler Express
Congratulations to 👏 Dana DeVries 👏 of Holland, Michigan, winner of last week’s Riddler Express!
Last week, disaster struck your city and you and all your neighbors were permanently evacuated — but your street and its row of 36 houses will remain, at least for a while. Within two years, the worst-maintained row house collapses. Within two more years, any houses neighboring that collapsed house also collapse, as will the second-worst-maintained house at the time of the initial evacuation, if it hasn’t collapsed already. Both these contagious and maintenance-based collapses continue in this fashion every two years. Assuming a random distribution of poorly maintained homes, what is the longest your home can remain standing? What is the fewest number of years it will take for all 36 houses to collapse?
First: The longest your home can remain standing is 72 years after the disaster strikes. For this situation, the best-case scenario is that you have both the best-maintained house on the street and that it’s located on the far end, with the houses getting more and more poorly maintained as you move away from your own house. That means the first house to collapse will be the one furthest away from you, and it will be followed by the house next to it, and in two years by the house next to it, and so on. This minimizes the collapse-contagion and buys you two years for each of the 36 houses on the street, which gives yours 72 years to stand.
Second: The quickest that all 36 houses can collapse is 12 years. In this case, we want not to minimize the collapse-contagion but to maximize it. We want the “naturally” collapsing houses to have standing neighbor houses so that those can soon collapse, too. If we arrange the houses just so, we’ll witness the following pattern. In the first two years, one house collapses. In the second two years, three more houses collapse — one new house and two houses neighboring the earlier collapsed house. After two more years, five more houses collapse — one new house and four houses neighboring earlier collapsed houses. After two more years, seven more collapse. And so on. 1 + 3 + 5 + 7 + 9 + 11 = 36, so it takes six steps, or 12 years. (Note that the sum of the first k odd numbers is equal to \(k^2\).)
So in general, for a street of N houses, the longest any of them will stand is 2N years and the quickest they’ll all go is \(2\sqrt{N}\) years, rounded up.
Need to visualize it? Bill Tressler built a crumbling dystopia simulator, and Hernando Cortina beautifully plotted the slow and inevitable destruction of your street over time:
Solution to last week’s Riddler Classic
Congratulations to 👏 Brad Slavens 👏 of Atlanta, winner of last week’s Riddler Classic!
Last week, you had a business decision to make. You ran a road building company, and a state offered you a $28 million contract to connect four towns with roads in some way. The towns were arranged as corners of a square with sides 10 miles long, and a mile of road cost you $1 million to build. Could you turn a profit if you took the job?
Yes, indeed you could! In fact, you could profit as much as about $680,000.
Some obvious arrangements of roads would put you in the red. For example, if you built a square, connecting the four towns along a single perimeter, it’d cost you $40 million. If you built an “H,” with two three-way intersections on either side, it’d cost you $30 million. If you built an “X,” connecting the towns with one four-way interchange in the middle, it’d cost you two diagonals, or about $28.3 million. None of these are quite efficient enough.
But we can still improve. Imagine taking the “H” arrangement and pinching its two intersections horizontally inward a bit, toward the land in the middle of the four towns. We’d wind up with a road system that looks like this, as illustrated by Jonathan Williams:
Solver Tess Huelskamp dubbed this arrangement the “TIE fighter.” And Jonathan explained: “The planet’s best civil engineers have already solved this problem of how to connect a lattice of points with the least material, and we call it the honeycomb.” Bees!
But how much will our TIE fighter/honeycomb cost to build? We can use a little calculus, as solver David Nusbaum explained. First, place the cities on a grid at the points (5, 5), (5, -5), (-5, 5) and (-5, -5), such that there are 10 miles on each side of the square. We want to find a distance \(x\) — the distance our intersections have been “pinched” — that minimizes the total length of road we must build. (For example, if \(x = 5\) we’ve built the “H” shape and if \(x = 0\) we’ve built the “X” shape mentioned above.) The total distance of road we must build for some given x is
\begin{equation*}D(x) = 4 \sqrt{5^2 + (5-x)^2} + 2x\end{equation*}
The first part in this equation is the four diagonal pieces, which comes from the Pythagorean theorem, and the second part is the central horizontal piece. To minimize this, we can take its derivative and set it equal to zero:
\begin{equation*}2 – \frac{4(5-x)}{\sqrt{x^2 -10x+50}} = 0\end{equation*}
Solving this gives \(x=5-\frac{5}{\sqrt{3}}\), for a total road distance of \(10\sqrt{3}+10\) or about 27.32 miles. That’ll cost us about $27.32 million to build, and our fee is $28 million. We just made $680,000!
This road-building business exercise is an example of a famous class of problems called Steiner tree problems, after the Swiss geometer Jakob Steiner. In general, the goal of these is to connect objects in an optimal way. They have applications not just in hypothetical road-building but also in circuit board design.
Remarkably, you could also have solved this puzzle not only with a hive of bees but also with soap bubbles. Because of the way the surface tension works, a soap film is stable only if its area is minimized. “This is a an inexhaustible source of mathematically significant experiments,” the authors of “What Is Mathematics?” wrote.
What about other shapes of towns? Laurent Lessard illustrated the solutions for regular polygonal arrangements for three, four and five towns. They have one, two and three “Steiner points” — created interior intersections in our case — respectively.
For shapes with more sides, however, this pattern falls apart, Laurent explained, and the shortest path is simply a set of roads most of the way around the perimeter:
Finally, Zach Wissner-Gross showed us what happens if we’re dealing not with towns but rather with space stations.
Riddler Nation is coming for you, Elon.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.