Welcome to The Riddler. Every week, I offer up a problem related to the things we hold dear around here — math, logic and probability. These problems, puzzles and riddles come from lots of top-notch puzzle folks around the world, including you, the readers. You’ll find this week’s puzzle below.
Mull it over on your commute, dissect it on your lunch break, and argue about it with your friends and lovers. When you’re ready, submit your answer using the form at the bottom. I’ll reveal the solution next week, and a correct submission (chosen at random) will earn a shoutout in this column. Important small print: To be eligible for the shoutout, I need to receive your correct answer before 11:59 p.m. EST on Sunday — have a great weekend!
Before we get to the new puzzle, let’s celebrate the solver of last week’s. Congratulations to 👏 Laurens De Koster 👏 of Brussels, Belgium, our big winner. You can find a solution to the previous Riddler at the bottom of this post.
Now, here’s this week’s Riddler. It’s a twist on a classic that comes to us from Chris Scambler, a philosophy Ph.D. student at New York University:
You’re on the north shore of a river, and want to cross to the south, via a series of 13 bridges and six islands, which you can see in the diagram below. But, as you approach the water, night falls, a bad storm rolls in, and you’re forced to wait until morning to try to cross. Overnight, the storm could render some of the bridges unusable — it has a 50 percent chance of knocking out each of the bridges. (The chance is independent for each bridge.)
Illustration by Ella Koeze
Question 1: What’s the probability you will be able to cross the river in the morning? (You have no boat, can’t swim, can’t fix the bridges, etc. No tricks.)
Now imagine a different, wider river, with many more islands — in fact, arbitrarily many. Specifically, imagine that the islands are arrayed in an N-rows-by-N+1-columns grid — similar to before, where N happened to equal two — and connected by bridges to each adjacent island in the same way. Each island adjacent to the shore is also connected by a bridge to the shore. It would look something like this:
Illustration by Ella Koeze
Question 2: What’s the probability you’ll be able to cross this river in the morning, after the same storm — with the same independent 50 percent chance of knocking out each bridge — rolls through?
Extra credit: In addition to the arbitrarily large N-by-N+1 array of islands, it seems like this problem could admit many other cool extensions. Create, describe and analyze a twist on this problem, and you’ll be eligible for my inaugural 🏆 Coolest Riddler Extension Award 🏆. Alter the storm’s strength, rearrange the bridges, vary their types, or something even more creative. Submit a description in the form below, or shoot me a link to your work on Twitter.
Need a hint? You can try asking me nicely. Want to submit a puzzle or problem? Email me.
[googleapps domain=”docs” dir=”forms/d/1gv_soUYC06YlLZTJ3etvOBmM_OwX_CgNpTWck_eowxE/viewform” query=”embedded=true” width=”760″ height=”1250″ /]
| SUBMITTED ANSWER | PERCENT OF SUBMISSIONS |
|---|---|
| 2/3 | 43.6% |
| 50/99 | 35.2 |
| 1/2 | 8.6 |
| 1 | 1.2 |
| Other* | 11.4 |
Last week’s Riddler from Mike Donner concerned a neurotic free-throw shooter. The answers rolled in — via the appropriate electronic form, but also on paper plates and cocktail napkins — and a healthy 43.6 percent of submissions were correct. But this one proved polarizing, as you can see in the table below.
The correct answer is two-thirds, or 66.666… (repeating) percent. Here’s one (very rigorous) proof, adapted from that of our winner, Laurens De Koster:
Let \(H(n)\) be the number of shots hit after \(n\) shots have been taken. Given the shooter’s specific neurosis, the probability of hitting shot No. 100 is \(H(99)/99\), or, since the coach saw him make shot No. 99, \((H(98)+1)/99\).
To determine the probability distribution of \(H(98)\), we can apply Bayes’s theorem. The probability of \(H(98)=m\) (\(m\) will range from 1 to 97), given that shot No. 99 was hit, is the probability of hitting shot No. 99 given \(H(98)=m\), multiplied by the probability of \(H(98)=m\) (in a vacuum), divided by the probability of hitting shot No. 99 (in a vacuum). Algebraically, that looks like this:
$$p(H(98)=m | \text{No. 99 made}) = \frac{p(\text{No. 99 made} | H(98)=m)\cdot p(H(98)=m)}{p(\text{No. 99 made})}$$
We can also prove that, for all \(N\geq 3\) and for \(H\) and \(m\) from 1 to \(N-1\), \(p(H(N)=m)=1/(N-1)\). In other words, the probability that the shooter has made \(m\) shots in \(N\) attempts is one divided by the number of attempts minus one.
For example, for \(N=3\), it’s trivial that \(p(H(3)=1) = p(H(3)=2) = 1/2\).
For \(N>3\), the probability of \(H\) shots having been hit is the probability of hitting a shot with \(H-1\) on the board, plus missing a shot with \(H\) on the board:
\begin{equation} \begin{split}p(H(N+1)=m) & =m/N\cdot p(H(N)=m-1)+(1-(m+1)/N)\cdot p(H(N)=m) \\ & = m/N\cdot 1/(N-1)+1/(N-1)-m/(N\cdot (N-1)) \\ & = 1/N \end{split} \end{equation}
This means that, after shot No. 98, all numbers of total made shots, from one to 97, are equally likely, each having probability 1/97. (One implication of this is that it doesn’t matter how many shots the coach was absent for — the right answer would remain the same!)
The probability of hitting shot No. 99 is then 1/2, or the weighted sum of the probabilities: \(\sum_{i=1}^{97}(1/97\cdot (i/98)) = 1/97\cdot 1/2\cdot 97\cdot 98/98 = 1/2\).
Going back to Bayes’s theorem, we can calculate that
$$p(H(98)=m | \text{No. 99 made}) = (m/98\cdot 1/97)/(1/2) = 2m/(97\cdot 98)$$
The probability of hitting shot No. 100 is a weighted sum of the probabilities that \(H\) is some given number, and that the player will hit the next shot given \(H\).
\begin{equation} \begin{split}p(\text{No. 100 made} | \text{No. 99 made}) & = \sum_{i=1}^{97} {2\cdot i/(97\cdot 98) \cdot (i+1)/99 } \\ & = 2/(97\cdot 98\cdot 99) \cdot \sum_{i=1}^{97}{i^2} + \sum_{i=1}^{97}{i} \\ & = 2/(97\cdot 98\cdot 99) \cdot (1/6\cdot 97\cdot 98\cdot 195 + 1/2\cdot 97\cdot 98) \\ & = 1/99 \cdot (1/3 \cdot 195 + 1) \\ & = 2/3\end{split} \end{equation}
You can also arrive at this solution in many other ways and, as usual, many of you lionhearted Riddler solvers went above and beyond. Mesmerizing graphs, like this, proliferated:
The crew over at BoardGameGeek provided lively discussion of the problem. And you can view a video simulation of the free throws, created by reader Andrew Kniss, here: