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 the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Nation is competing against Conundrum Country at an Olympic archery event. Each team fires three arrows toward a circular target 70 meters away. Hitting the bull’s-eye earns a team 10 points, while regions successively farther away from the bull’s-eye are worth fewer and fewer points.
Whichever team has more points after three rounds wins. However, if the teams are tied after each team has taken three shots, both sides will fire another three arrows. (If they remain tied, they will continue firing three arrows each until the tie is broken.)
For every shot, each archer of Riddler Nation has a one-third chance of hitting the bull’s-eye (i.e., earning 10 points), a one-third chance of earning 9 points and a one-third chance of earning 5 points.
Meanwhile, each archer of Conundrum Country earns 8 points with every arrow.
Which team is favored to win?
Extra credit: What is the probability that the team you identified as the favorite will win?
The solution to this Riddler Express can be found in the following column.
From Eli Luberoff (courtesy of Iñaki Huarte) comes a geometric curiosity:
Suppose you have a chain with infinitely many flat (i.e., one-dimensional) links. The first link has length 1, and the length of each successive link is a fraction f of the previous link’s length. As you might expect, f is less than 1. You place the chain flat on a table and some ink at the very end of the chain (i.e., the end with the infinitesimal links).
Initially, the chain forms a straight line segment, and the longest link is fixed in place. From there, the links are constrained to move in a very specific way: The angle between each chain and the next, smaller link is always the same throughout the chain. For example, if the Nth link and the N+1st link form a 40 degree clockwise angle, then so do the N+1st link and the N+2nd link.
After you move the chain around as much as you can, what shape is drawn by the ink that was at the tail end of the chain?
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to 👏 Jackson 👏 of Salt Lake City, Utah, winner of last week’s Riddler Express.
Last week, you navigated an 8-by-8 chessboard, each of whose squares had one piece. You began at the white bishop on the green square. You could then move from white piece to white piece via the following rules:
- If you were on a pawn, you could move up one space diagonally (left or right).
- If you were on a knight, you could move in an “L” shape — two spaces up, down, left or right, and then one space in a perpendicular direction.
- If you were on a bishop, you could move one space in any diagonal direction.
- If you were on a rook, you could move one space up, down, left or right.
- If you were on a queen, you could move one space in any direction (horizontal, vertical or diagonal).
For example, suppose your first move from the bishop was diagonally down and to the right. You would then be at a white rook, so your possible moves were left or up to a pawn or right to a knight.
Your objective was to reach one of the four black kings on the grid. However, at no point could you land on any of the other black pieces. (Knights were allowed to hop over the black pieces.)
What sequence of moves allowed you to reach a king?
It so happened that there were multiple solutions here. Solver Tо̄saka Rin of Kobe, Japan, started by working backwards from the four kings. The king in the top right could only be reached by the knight two squares down and one square to its left. The king in the top middle could be reached both by the rook one square to its right and the knight one square down and two squares to its left. The king in the top left could only be reached by the knight one square down and two squares to its right. Meanwhile, there was no way to reach the king in the bottom left corner.
Solver Andrew Heairet was kind enough to animate a few of the resulting solutions:
While most solvers worked out a viable pathway by hand, some, like David Wanner of St. Louis, wrote code to do it for them. I bet it took a little longer, but was just as glorious.
Solution to last week’s Riddler Classic
Congratulations to 👏 Austin Shapiro 👏 of Oakland, California, winner of last week’s Riddler Classic.
Last week marked the beginning of the Summer Olympics! One of the brand-new events this year is sport climbing, in which competitors try their hands (and feet) at lead climbing, speed climbing and bouldering.
You assumed the event’s organizers accidentally forgot to place all the climbing holds and had to do it last-minute for their 10-meter wall, which was the regulation height for the purposes of this riddle. Climbers didn’t have any trouble moving horizontally along the wall. However, climbers couldn’t move between holds that were more than 1 meter apart vertically.
In a rush, the organizers placed climbing holds randomly until there were no vertical gaps in excess of 1 meter between climbing holds (including the bottom and top of the wall). Once they were done placing the holds, how many were there on average (not including the bottom and top of the wall)?
Unlike last week’s Express, this puzzle was perhaps better solved (or at least approximated) via simulation. Most solvers wrote some code that added climbing holds one at a time, checking for the largest gap between neighboring holds after each addition. As long as this largest gap was greater than 1 meter, then you should have added another hold! Otherwise, you then recorded how many were placed and simulate the whole thing over again.
This is precisely what solver Peter Ji did. After 10,000 simulations, Peter found that the organizers placed about 43 climbing holds on average. Meanwhile, Rohan Lewis was able to be a little more precise by running a total of 10 million simulations, finding the average number of holds was closer to 43.05.
Meanwhile, a few solvers were able to find the exact solution analytically, albeit with the help of a computer. Finding the probability distribution for the largest spacing between values chosen randomly from a uniform distribution is not a new problem.
As discussed by solver Peter Norvig (who in turn gives a tip of the hat to George Hauser), if you were to pick any k gaps (among the N+1 gaps created by N holds), the probability that they were all greater than one-tenth of the wall’s height was given by the expression (1−0.1k)N, as long as k was less than or equal to 10. Without getting deep into the complexities of order statistics, this result makes some intuitive sense — as both k and N increase, the probability that all the gaps exceed one-tenth of the wall diminishes. And since gaps couldn’t overlap, there was no way for 11 or more gaps to all be at least one-tenth of the wall’s height.
Even with this result in hand, there was still quite a bit of math to do. Peter used the probability that any k gaps were all greater than 1 meter to compute the probability that exactly one — the largest gap — was greater than 1 meter. He started by adding up all the probabilities where at least one specific gap exceeded 1 meter. However, this overcounted the cases where at least two gaps both exceeded 1 meter, so these probabilities had to be subtracted off. This result then undercounted cases where at least three gaps all exceeded 1 meter, and so on.
Using the probability that exactly one gap was greater than 1 meter, you could compute the probabilities for each number of holds. For example, the probability that the organizers had to add exactly 30 holds was equal to the probability that there was a gap greater than 1 meter at 29 holds and that there was no such gap at 30 holds. After some further simplification, Peter hits the nail on the head: The average number of holds is approximately 43.04683.
For extra credit, the climbers found it just as difficult to move horizontally as vertically, meaning they couldn’t move between any two holds that were more than 1 meter apart in any direction. You were also told that the climbing wall was a 10-by-10 meter square. If the organizers again placed the holds randomly, how many had to be placed on average until it was possible to climb the wall?
As if the one-dimensional version of this puzzle wasn’t hard enough, now there were two dimensions to consider! This was especially tricky, since viable paths up the climbing wall were allowed to go down as well as up, as demonstrated by some of Peter’s simulations:
Over the course of 1 million simulations, solver Emily Boyajian added one climbing hold at a time, keeping track of whether it was accessible via the bottom or made any other holds accessible. Once a hold was accessible from the top of the wall, the simulation ended. With this approach, Emily found that the answer was very close to 143.
Those were a lot of holds. Hopefully the Olympic organizers don’t plan on placing them randomly.
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 firstname.lastname@example.org.