Welcome back 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.
Thanks for waiting out my vacation for the past two weeks. I am refreshed and ready to puzzle. Here we go again, onward, through the mathematical mists …
Riddler Express
From Chris Hopkins, the probabilities lurking within a slowly crumbling dystopia:
You live in a row house, one of 36 like it on your side of the block. A disaster strikes, and the city has to be evacuated. Two years later, with everyone gone for good, the worst-maintained row house on your side of the block, battered by the elements for too long, collapses. Within two years, any row house neighboring the collapsed one also collapses — as does the second-worst-maintained home on the block, if it wasn’t next to the worst-maintained one.
This contagion continues: Every two years, any row house next to one that’s already collapsed also becomes rubble, and houses continue to collapse in order of how badly maintained they are — the third-worst-maintained house falls in the third round, the fourth-worst-maintained in the fourth round, and so on, assuming they were still standing at the start of that round. (The maintenance rankings are set at the moment the city is evacuated and don’t change from round to round.) Assuming a random distribution of poorly maintained homes, what’s the longest your home can remain standing? What’s the fewest number of years it will take for all 36 row houses to collapse?
Extra credit: How does either answer change for N rowhouses?
Riddler Classic
From David Seal, a classic construction problem perfect for Infrastructure Week:
Consider four towns arranged to form the corners of a square, where each side is 10 miles long. You own a road-building company. The state has offered you $28 million to construct a road system linking all four towns in some way, and it costs you $1 million to build one mile of road. Can you turn a profit if you take the job?
Extra credit: How does your business calculus change if there were five towns arranged as a pentagon? Six as a hexagon? Etc.?
Solution to the previous Riddler Express
Congratulations to ÑÑâÐ Jay Lee ÑÑâÐ of Portland, Oregon, winner of the previous Riddler Express!
At the grocery store you work at, the evening manager assigns 15 grocery aisles to the five night stockers who work that shift. Assume that the aisles are assigned randomly. How many different ways can you be assigned three aisles out of the 15? How many different ways are there to assign the 15 aisles to the five stockers, assuming they are each assigned three aisles? And finally, if the manager can assign any number of aisles to any stocker, how many possibilities are there?
First, there are 455 ways you might be assigned three aisles out of the 15. There are 15 possibilities for your first aisle, 14 for your second, and 13 for your third, giving (15)(14)(13) = 2,730. But we don’t care about the specific order in which you get assigned these aisles, so we can divide that by the number of orders in which these aisles might have been assigned, which is (3)(2)(1) = 6, giving us 2,730/6 = 455. Another way to put all this: It’s just “15 choose 3,” or \({15 \choose 3}\).
Second, there are 168,168,000 ways the 15 aisles might have been assigned to the five stockers, assuming you are each assigned three aisles. Essentially, we can repeat the solution above but for you and your four co-workers. There are “15 choose 3” ways for you to be assigned your aisles, then “12 choose 3” ways for the next stocker to be assigned hers, then “9 choose 3” for the stocker after that, and so on, and we can multiply all of these together to find the total. Mathematically, that looks like
\begin{equation*}{15 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3} = 168,168,000\end{equation*}
Third, if the manager can assign any number of aisles to any stocker, there are 30,517,578,125 ways she might do it. For any given aisle of the 15, there are five stockers to whom it might be assigned. That makes \(5^{15}\), or 30,517,578,125, possibilities.
Solution to the previous Riddler Classic
Congratulations to ÑÑâÐ Curt Nehrkorn ÑÑâÐ of Davis, California, winner of the previous Riddler Classic!
Running is more fun when you have someone to run with, but you only want to run with someone if they run about as fast as you do. Perhaps if enough people run together, it becomes more likely that everyone has a running buddy. Last week, N people went for a run, and each person’s preferred running speed, call it \(X_i\), was independent and normally distributed, with a mean of \(\mu\) and a variance of \(\nu^2\).
Each person had a running buddy if there was another person in the group whose preferred speed was about the same as theirs. Specifically, person \(i\) and person \(j\) could be running buddies if their preferred speeds were within some number \(s\) of each other — that is, if \(|X_i – X_j | \leq s\). How large did N need to be before the probability of each person having a running buddy was 99 percent?
This one gets pretty (read: extremely) mathy, but hey, this is the Riddler Classic, people! If it were easy, everybody would do it. This puzzle’s submitter, Jay Hennig, walks us through it. Take it away, Jay:
First, we want to find the probability that for person \(i\), there is a running buddy \(j\) such that \(|X_i – X_j | \leq s\) — that is, someone else with a similar enough preferred speed. This is the same as saying that the minimum of \(|X_i – X_j |\), for all \(j\neq i\) is less than \(s\). So the probability that person \(i\) will have a running buddy is
\begin{align*}p_i & = P(\min_{j \neq i} |X_i – X_j | \leq s)\\& = 1 – \prod_{j \neq i} P(|X_i – X_j | > s)\\& = 1 – \prod_{j \neq i} (1 – P(|X_i – X_j | \leq s))\\& = 1 – (1 – G(s))^{N-1}\\& = 1 – \left(1 – \text{Erf} \left(\frac{s}{2v}\right)\right)^{N-1}\end{align*}
In what’s above, \(G(s) = \text{Erf}(s/2v)\) is the cumulative distribution function of \(|X_i – X_j |\) and “Erf” is the Gauss error function.
Now that we’ve found \(p_i\), we need to find \(N\) such that \(p_i \geq \alpha = 0.99\).
\begin{align*}p_i & = 1 – \left(1 – \text{Erf}\left(\frac{s}{2v}\right)\right)^{N-1} \geq \alpha\\& \Rightarrow 1-\alpha \geq \left(1 – \text{Erf}\left(\frac{s}{2v}\right)\right)^{N-1}\\& \Rightarrow \log(1-\alpha) \leq (N-1) \log\left(1 – \text{Erf} \left(\frac{s}{2v}\right)\right)\\& \Rightarrow N \geq 1 + \frac{\log(1-\alpha)}{\log\left(1 – \text{Erf} \left(\frac{s}{2v}\right)\right)}\end{align*}
Phew! Let’s use data from last year’s Boston Marathon to get some actual numbers rather than just a bunch of equations. The black curve below represents the real runner data, and the red curve is a fitted normal distribution:
Turns out the speed of real runners does appear to be about normally distributed. So when we apply the parameters of our puzzle to the real data set, the mean \(\mu\) is about 6.8 and the variance \(\nu^2\) is about \(1.16^2\).
As far as \(s\) goes, let’s guess that runners would be OK with their buddy’s speed being somewhere within 0.25 and 1 mph of their own. With these assumptions, to be 99 percent confident that everyone has a running buddy, we would need about 17.8 runners — so a group of 18 would do. Here’s a plot of the probability of having a running buddy for various values of \(N\) and \(s\), with the 99 percent level marked for reference:
It’s good to have a buddy.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.