7 June 2022

Desert Dwellers (03/06/22 Riddler Classic)

Original puzzle

This problem is a relatively simple exercise in combinatorics. Assume the oasis is the $x$-axis of an infinite Cartesian plane. Each traveller picks a random point on the oasis and chooses a random angle uniformly distributed on $[-\pi,\pi]$ for their ray.

Separate the travellers into two groups: those travelling into the upper half plane (ie. a positive angle) and those into the lower half plane (ie. negative angle). Paths do not intersect iff for each group, the travellers are lined up in order of angle.

Suppose there are $M$ travellers in the upper-half-plane group. This situation occurs with probability \[\frac{1}{2^N}{N\choose M}\]

There are exactly ${N\choose M}$ ways to organise the travellers such that no paths intersect. Given there are a total of $N!$ permutations of the travellers, this means the probability of no intersecting paths is \[\frac{1}{N!}{N\choose M}\]

And so the desired probability of no intersecting paths overall is

\[\begin{align*}\text{Prob}&=\sum^N_{M=0}\frac{1}{2^NN!}{N\choose M}^2\\&=\frac{1}{2^NN!}{2N\choose N}\\&=\frac{(2N)!}{2^N(N!)^3}\end{align*}\]