June 20, 2021
Eight two-way roads all converge at a single intersection, as shown in the diagram below.
Two cars are heading toward the single intersection from different directions chosen at random. Upon reaching the intersection, they both turn in a random direction (where proceeding straight is a possible “turn”) — however, neither car pulls a U-turn (i.e., heads back the way it came).
In some cases, the paths of the cars can be drawn so that they do not cross. In this case, all is well.
However, in other cases, the paths must cross. In this event, the cars will crash.
What is the probability the cars will crash? (If both cars head off in the same direction, that also counts as a crash.
Extra credit: As the number of two-way roads converging at the intersection approaches infinity, what value does the probability of crashing approach?
Explanation:
The most elegant way to approach this problem is to model the two-car problem in the following manner:
The reason why this can lead to the answer in a straightforward fashion is because we can think of the eight-road intersection as a "circle". The route of the first car, defined by, say the blue path in the diagram shown above, essentially "cuts" the circle into two pieces. Then, the path of the second car, defined by the red path, would be completely determined by the starting and the destination roads selected for it. If both the starting and the ending points are within the "slice" encompassed by the first car's route (i.e. the blue path), then there will be no crash. Otherwise a crash occurs.
Here I am assuming that if the second car starts on the same road as the first car's turning road, then there will be NO crash since the two roads are not driven by those cars at the same time. The turns do not overlap here. The second car cannot start on the same road as the first car. Furthermore, let us assume that if two cars merge onto the same road, then that's a crash as well.
Without loss of generality (WLOG), let the first car travel from due west. It has an equally likely probability of selecting the 7 possible routes, so the probability for each route is \(\frac{1}{7}\). Say the first car selects to make a sharp right and go towards the southwest corner. There are now two slices of our pizza pie: one tiny slice making up \(\frac{1}{8}\) of the circle and the other making up \(\frac{7}{8}\). We divide the second car's selections into two parts. For the first part, let us consider the second car starting on the same road as the first car's turning road. In that case, ALL roads except for the starting road of the second car will avoid the crash, and the probability of no crash is simply \(\frac{1}{7}\), i.e. the probability that the second car selected that road. If the second car did not select that road, i.e. with probability of \(\frac{6}{7}\), then the car is either within the smaller slice or the larger slice. For the first case, that is impossible, and for the latter, there are 6 choices of starting and 6 choices of turning roads given probability of no crash to be \(\left(\frac{6}{7}\right)^2\). Therefore, for this route, the probability of no crash is \(\frac{1}{7} + \left(\frac{6}{7}\right)^2\).
Similarly, if the first car selects the W-S route, then the entire pizza is sliced into two pieces: \(\frac{2}{8}\) and \(\frac{6}{8}\) (I didn't reduce the fractions so that I can explicitly show the road divisions). For this route, the second car avoids the crash, once again, if it can entirely stay within one of the two slices or if travelling along the boundary. For the latter case, the crash avoidance probability is once again \(\frac{1}{7}\). In the first case, if the car stays within the smaller slice, the probability of avoiding the crash is: \(\left(\frac{1}{7}\right)^2\) (remember the second car CANNOT merge onto the same turning road as the first car!), and for the bigger slice, \(\left(\frac{5}{7}\right)^2\). The key observation here is that there will be \((n - 1)\) possible starting AND destination roads for the second car to stay inside the \(\frac{n}{8}\) slice of the pizza out of the possible 7 routes, and those selections are independent of each other. So the probability of avoiding the crash is \(\frac{1}{7} + \left(\frac{1}{7}\right)^2 + \left(\frac{5}{7}\right)^2\).
Therefore, in general, the probability of avoiding the crash for the second car given the route selected by the first car with 8 roads and therefore 7 routes is:
\begin{align} P(\text{No Crash}) &= P(\text{No Crash} | \text{Route Selected}) P(\text{Route Selected}) \\ &= \left(1 + \frac{2(1^2 + 2^2 + \dots + 6^2)}{7^2}\right)\left(\frac{1}{7}\right) \\ &= \frac{33}{49} \end{align}
Finally, for probability of crash:
\begin{align} P(\text{Crash}) &= 1 - P(\text{No Crash}) \\ &= 1 - \frac{33}{49} \\ &= \boxed{\frac{16}{49}} \\ & \approx 0.327 \end{align}
We can generalize this to \(N + 1\) roads, where \(N\) is the number of possible routes the cars can take (with \(N + 1\) roads).
\begin{align} P(\text{Crash}) &= 1 - P(\text{No Crash}) \\ &= \boxed{1 - \left(\frac{1}{N}\right)\left(1 + \frac{2(\sum_{k = 1}^{N-1} k^2)}{N^2}\right)} \end{align}
The easy way is just to let \(N \to \infty\) and evaluate the probability of crash in terms of N taken to that limit. For sake of completeness, it is given below:
\begin{align} P(\text{Crash}) &= \lim_{N \to \infty} 1 - \left(\frac{1}{N}\right)\left(1 + \frac{2(\sum_{k = 1}^{N-1} k^2)}{N^2}\right) \\ &= 1 - \lim_{N \to \infty} \left(\frac{1}{N}\right)\left(1 + \frac{2(\sum_{k = 1}^{N-1} k^2)}{N^2}\right) \\ &= 1 - \lim_{N \to \infty} \frac{2N^3 - 3N^2 + N}{3N^3} \\ &= 1 - \frac{2}{3} \\ &= \frac{1}{3} \end{align}
But that's boring. Let's complete the circle, literally, and imagine a disc. Let a blue dot be a point on the edge of the disc, travelling inward towards the center on a straight line, and then makes a "cut" and travel on another radius towards the edge again. Doing so effectively cuts the disc into two pieces: \((\theta, 2 \pi - \theta)\), for \(0 < \theta < 2\pi\). Once again, we need to apply the same steps we did in the original, discrete problem and consider the probability of the second car, the red dot, avoiding the crash. To do so, the second car must start AND end within the same slice. WLOG, let the disc have unit radius. Therefore, the probability of staying in the \(\theta\) slice is \(\left(\frac{\theta}{2\pi}\right)^2\) and similar for the other slice it is \(\left(\frac{2\pi - \theta}{2\pi}\right)^2\). The probability of avoiding a crash for any selected route by the first car, the blue dot, would be \(\left(\frac{\theta}{2\pi}\right)^2 + \left(\frac{2\pi - \theta}{2\pi}\right)^2\).
Again, the routes are equally likely to be selected, and hence we have an expression for the probablity of non-crash:
\begin{align} P(\text{No Crash}) &= \int_{\theta = 0}^{\theta = 2\pi} \frac{\left(\frac{\theta}{2\pi}\right)^2 + \left(\frac{2\pi - \theta}{2\pi}\right)^2}{2\pi} \mathrm{d}\theta \\ &= \frac{1}{8\pi^3} \int_0^{2\pi} (\theta^2 + 4\pi^2 - 4\pi \theta + \theta^2) \mathrm{d}\theta \\ &= \frac{1}{8\pi^3} \int_0^{2\pi} (2\theta^2 + 4\pi^2 - 4\pi \theta) \mathrm{d}\theta \\ &= \left.\frac{1}{8\pi^3} \left(\frac{2\theta^3}{3} - 2\pi \theta^2 + 4\pi^2 \theta\right)\right|_0^{2\pi} \\ &= \frac{1}{8\pi^3} \left(\frac{16\pi^3}{3} - 8\pi^3 + 8\pi^3\right) \\ &= \frac{16\pi^3}{24\pi^3} \\ &= \frac{2}{3} \end{align}
Therefore, for probability of crash:
\begin{align} P(\text{Crash}) &= 1 - P(\text{No Crash}) \\ &= 1 - \frac{2}{3} \\ &= \boxed{\frac{1}{3}} \end{align}
The second car is twice likely to not crash into the first car as the roads increase! Quite safe I'd say!