Escaping the Desert
Pobability; Difficulty: easy
A Sandy Puzzle
The Riddler Classic from this week (Jun 3rd, 2022) at first glance might appear to be a geometry /alegbra/calculus problem; but is a straightforward combinatorial probability exercise. Here’s the Classic reproduced:
From Jason Zimba comes a surprisingly sandy puzzle:
In the Great Riddlerian Desert, there is a single oasis that is straight and narrow. There are N travelers who are trapped at the oasis, and one day, they agree that they will all leave. They independently pick a random location in the oasis from which to start and a random direction in which to travel. Once their supplies are packed, they all head out.
What is the probability that none of their paths will intersect, in terms of N? (For the purposes of this puzzle, assume the oasis is a line segment, while the desert is an infinite Cartesian plane.)
*spoiler alert* solution and answer follow in the sections below.—
Solution
This puzzle shares similarities with Zach’s Robo Pizza puzzle in that what appears to be about geometry is in actuality a combinatorial probability exercise.
Assume a vertically oriented Oasis segment OS as shown in the figure below using \(N = 7\) travelers for illustration. A few (obvious) observations lead to the solution:
- Since we are dealing with an infinite planar desert, the actual separation distances between the travelers starting points has no bearing on their intersection as long as they choose distinct points—which they are guaranteed to by the puzzle
- Travelers who go to the right (in the orientation shown) can only have their paths intersect with those of other right going travelers, and will never intersect with those who chose left and vice versa
- The paths will not intersect only if travelers on each side have path angles (relative to the oasis strip) in strictly ascending (or descending, depending on how you measure it) order. In the example in the figure, paths A,B,C,D on the right satisfy this i.e. ordered in increasing angles, and hence do not intersect; not the case with E,F,G on the left where paths E and F intersect.
Let the \(N\) travelers choose their starting points on the oasis segment and their path directions. First consider the case with \(r\) of the \(N\) travelers randomly choosing to go right and the remaining \(N-r\) going left:
Since the travelers paths are chosen randomly, right vs. left is essentially a coin flip. Hence the probability that you have \(r\) of the \(N\) travelers choosing to go right and the remaining \(N-r\) going left is binomially distributed with:
\[
P(r \textit{ go right, } N-r \textit{ go left}) \ = \ {N \choose r} \frac{1}{2^n}
\]
where the first expression is just the number of ways to choose \(r\) travelers from a total of \(N\).
Now consider the \(r\) rightward travelers’ random paths. Exactly 1 out of the \(r!\) equally likely possible orderings of the path angles/directions has them ordered in purely ascending order and hence non intersecting. All others will have at least 1 intersection. Similarly and independently for the \(N-r\) on the left. Hence the probability of no intersection in this case is:
\[
P(\textit{no intersections} \ | \ r \textit{ go right, } N-r \text{ go left}) \ = \ \frac{1}{r! \ (N-r)!}
\]
Now this was for the specific case of no intersections when \(r\) go right and the rest go left. The required probability for no intersections for the group of \(N\) can now be found using this result conditioning on there being \(r\) rightward travelers for all possible values of \(r\):
\begin{align*}
P(\textit{no intersections}) \ &= \ \sum_{r=0}^{N} \ P(\textit{no intersections} \ | \ r \textit{ go right, } N-r \text{ go left}) \ \cdot \ P(r \textit{ go right, } N-r \text{ go left}) \\ \\
&= \ \sum_{r=0}^{N} \ \frac{1}{r! \ (N-r)!} \ {N \choose r} \frac{1}{2^n} \\ \\
&= \ \sum_{r=0}^{N} \ \frac{N!}{r! \ (N-r)! \ N!} \ {N \choose r} \frac{1}{2^n} \\ \\
&= \ \sum_{r=0}^{N} \ \frac{1}{N!} \ \frac{1}{2^n} \ {N \choose r}^2 \\ \\
&= \ \frac{1}{N!} \ \frac{1}{2^n} \ \sum_{r=0}^{N} \ {N \choose r}^2 \\ \\
&= \ \frac{1}{N!} \ \frac{1}{2^n} \ {2N \choose N} \\ \\
&= \mathbf{{\color{Red} { \ \frac{(2N)!}{{2^n}{N!}^3} }}}
\end{align*}
The last expression above in red is the desired answer in terms of N. Note: Going from the third to last to the second to last equation makes use of this identity for the sum of squares of binomial coefficients.
Probability as N increases
One expects the likelihood of having no intersections to drop pretty fast as \(N\) increases. That’s exactly what happens: it’s 75% for two travelers and quickly drops to 2% with six travelers. The chart below illustrates this.
