Monday, June 21, 2021

Crash .... Into Me?

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.)

Let's deal instead with the general case of $N$ roads converging. We can label them $0$ through $N-1$ and without loss of generality assume that one of the cars always starts on the road labeled $0.$

Let's say that this first car starts on road $0$ ends up turning onto some road $k \in \{1, \dots, N-1\}.$ Then there will be a crash whenever (a) the second car starts on a road in $\{1, \dots, k-1\}$ and ends on a road in $\{k, \dots, N-1\}$ or (b) the second car starts on road a road in $\{k+1, \dots, N-1\}$ and ends on a road in $\{1, \dots, k\}.$ (Note explicitly that the car going from road $0$ to road $k$ will never crash with a car that starts on road $k.$)

The diagram below shows the $5$ case (a) crashes for $N=8$ and $k=3$ where the second car starts on road $1$.

Similarly, the diagram below shows the $3$ case (b) crashes for $N=8$ and $k=3$ where the second car starts on road $5.$
Since there are $(N-k)(k-1)$ combinations in case (a) and $(N-k-1)k$ combinations in case (b), if the first car starts on road $0$ and ends up turning onto road $k$, then there are $$(N-k)(k-1) + (N-k-1)k = (2k-1)N -2k^2$$ possible crashes.

Summing over all possible $k$ gives us a total of $$C_N = \sum_{k=1}^{N-1} (2k-1)N -2k^2 = N(N-1)^2 -\frac{1}{3}(N-1)N(2N-1) = \frac{N(N-1)(N-2)}{3}$$ crashes with $N$ converging paths. Since there are $(N-1)$ possible choices for the first car and $(N-1)^2$ possible choices for the second car, we get a crash probability with $N$ paths of $$p_N = \frac{C_N}{(N-1)^3} = \frac{N(N-1)(N-2)}{3(N-1)^3} = \frac{N(N-2)}{3(N-1)^2}.$$

In particular, when $N=8,$ we get $$p_8 = \frac{16}{49} \approx 32.65\%.$$ Also, as the number of paths increases, we get $$p_\infty = \lim_{N\to \infty} p_N = \frac{1}{3}.$$

No comments:

Post a Comment