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 Express
From Tom Hanrahan comes a maze for grandmasters:
The following 8-by-8 grid is covered with a total of 64 chess pieces, with one piece on each square. You should begin this puzzle at the white bishop on the green square. You can then move from white piece to white piece via the following rules:
- If you are on a pawn, move up one space diagonally (left or right).
- If you are on a knight, move in an “L” shape — two spaces up, down, left or right, and then one space in a perpendicular direction.
- If you are on a bishop, move one space in any diagonal direction.
- If you are on a rook, move one space up, down, left or right.
- If you are on a queen, move one space in any direction (horizontal, vertical or diagonal).
For example, suppose your first move from the bishop is diagonally down and to the right. Now you’re at a white rook, so your possible moves are left or up to a pawn or right to a knight.
Your objective is to reach one of the four black kings on the grid. However, at no point can you land on any of the other black pieces. (Knights are allowed to hop over the black pieces.)
What sequence of moves will allow you to reach a king?
The solution to this Riddler Express can be found in the following column.
Riddler Classic
Today marks 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.
Suppose the event’s organizers accidentally forgot to place all the climbing holds on and had to do it last-minute for their 10-meter wall (the regulation height for the purposes of this riddle). Climbers won’t have any trouble moving horizontally along the wall. However, climbers can’t move between holds that are more than 1 meter apart vertically.
In a rush, the organizers place climbing holds randomly until there are no vertical gaps between climbing holds (including the bottom and top of the wall). Once they are done placing the holds, how many will there be on average (not including the bottom and top of the wall)?
Extra credit: Now suppose climbers find it just as difficult to move horizontally as vertically, meaning they can’t move between any two holds that are more than 1 meter apart in any direction. Suppose also that the climbing wall is a 10-by-10 meter square. If the organizers again place the holds randomly, how many have to be placed on average until it’s possible to climb the wall?
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Brian Mercurio ÑÑâÐ of Binghamton, New York, winner of last week’s Riddler Express.
Last week, I found a brown 12-inch stick for my three dogs (Fatch, Fetch and Fitch) to play with. I marked the top and bottom of the stick and then threw it for Fatch. Fatch, a Dalmatian, bit it in a random spot — leaving a mark — and returned it to me. In her honor, I painted the stick black from the top to the bite and white from the bottom to the bite.
I subsequently threw the stick for Fetch and then for Fitch, each of whom retrieved the stick by biting a random spot. What was the probability that Fetch and Fitch both bit the same color (i.e., both black or both white)?
By and large, solvers took three different approaches here. First, you could have simulated thousands or even millions of random dog bites, and then counted up how often Fetch and Fitch both bit the same color. Angelos Tzelepis happened to simulate 5 million trios of bites, finding that 66.8 percent of them (a result suspiciously close to two-thirds) were the same color.
Meanwhile, Elaine H. of Tampa, Florida, arrived at an exact solution using calculus. Elaine set the length of the stick to 1 and supposed Fatch’s bite was a distance x from the top. The probability that Fetch and Fitch both bit above Fatch was then x2, while the probability they both bit below Fatch was (1−x)2. Adding these together gave the probability that Fetch and Fitch bit the same color: x2 + (1−x)2.
Since x was equally likely to take on any value between 0 and 1, you could find the total probability by integrating x2 + (1−x)2 from 0 to 1. Not surprisingly, this integral came to two-thirds, matching Angelos’ computational results.
Two approaches down, one to go. Solver Winston Luo leveraged the inherent symmetry in the puzzle. All three bites followed an identical uniform probability distribution, which meant all six relative orderings of the bites from top to bottom (Fatch-Fetch-Fitch, Fatch-Fitch-Fetch, Fetch-Fatch-Fitch, Fetch-Fitch-Fatch, Fitch-Fatch-Fetch and Fitch-Fetch-Fatch) were equally likely. Of these six permutations, Fetch and Fitch bit the same color in four of them — when Fatch was either the topmost or bottommost bite. And so the answer was four-sixths, which simplified to two-thirds.
Woof!
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Betts Slingluff ÑÑâÐ of Rockport, Massachusetts, winner of last week’s Riddler Classic.
Two weeks ago, Italy defeated England in a heartbreaking (for England) European Championship that came down to a penalty shootout. In a shootout, teams alternate taking shots over the course of five rounds. If, at any point, a team is guaranteed to have outscored its opponent after five rounds, the shootout ends prematurely, even if each side has not yet taken five shots. If the teams are tied after five rounds, they continue one round at a time until one team scores and another misses.
If each player had a 70 percent chance of making any given penalty shot, then how many total shots would have been taken on average?
As with last week’s Express, some solvers simulated thousands of shootouts to compute the average. Getting the stopping conditions was the trickiest part. After all, it was possible for the shootout to end after six shots, seven, eight, nine or 10 shots, or even in sudden death.
As tricky as it was to write code to simulate the shootout, solving it analytically was even trickier. Sanandan Swaminathan of San Jose, California, accomplished this by finding the probability the shootout would end for each number of shots.
As I mentioned, the fewest possible number of shots was six, when either team made its first three shots and the other team missed its first three (leaving it with two remaining shots — a guaranteed loss). The probability of this occurring was 0.73×0.33, then doubled, since either England or Italy could have been the team that went up 3-0. This came to a nice, even 0.018522.
Sanandan continued working through the increasingly complicated combinatorics to calculate the chances for each shootout duration: seven (with probability 0.076734), eight (0.14518602), nine (0.22835064) and 10 (0.2596431852).
But after 10 shots, you had to work out the math behind sudden death, which ended when one team made a shot and the other missed. The probability of this happening was 0.7×0.3, again doubled because either team could be the victor. This product was 0.42, which meant the average number of sudden death rounds played (if sudden death was reached) was 0.42 + 2×(0.58)1×0.42 + 3×(0.58)2×0.42 + 4×(0.58)3×0.42 + …. The sum of this infinite arithmetic-geometric series was 1/0.42, or about 2.381.
But wait! That was the average number of additional rounds. The average number of shots was twice this, since there were two shots per round. And so the additional number of shots was 2/0.42, or about 4.762.
Multiplying each of the respective number of shots by their probabilities, and then tacking on the 4.762 sudden death shots (again, in the event the shootout went to sudden death) resulted in an average total of approximately 10.47 shots, just edging into sudden death territory.
While the average number of shots was greater than 10, the median number was exactly 10, as shown by the frequency distribution Angelos generated below. This meant that, more often than not, the shootout did not go to sudden death.
Solver Grant Larsen worked out the more general case when the probability of any given goal being made was p. Defining y as the quantity p(1−p), Grant found that the average number of shots was 1/y + y(56 − y(203 − 4y(93 − 70y))). This was a fascinating result for two reasons. First, this function was symmetric about p = 0.5. So if each player had a 30 percent chance of making a goal, you’d get the same average number of kicks as when each player had a 70 percent chance.
Second, this meant the minimum occurred when players had a 50 percent chance of making any given shot, and this minimum was 10.03125 shots. In other words, when all the players have the same chance of making a goal, the average number of kicks will always exceed 10.
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 riddlercolumn@gmail.com.