This Riddler puzzle is a classic problem: how many lattice paths connect two points on a grid? Here is a paraphrased version of the problem.
The streets of Riddler City are laid out in a perfect grid. You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, you prefer to walk a different path along the streets each time. How many different paths are there? (Assume you don’t take paths that are longer than required). Your home is M blocks west and N blocks south of the office.
Here is my solution:
[Show Solution]
See the diagram below, where we start at $A$ and we’d like to get to $B$. In this version, Since we can only walk along roads, we must move East a total of $M$ times and north a total of $N$ times to arrive at our destination. This means we must walk $M+N$ blocks to get to work. Backtracking (moving south or west) will necessarily lead to paths that are longer than necessary, so we can exclude these cases.
Each path from A to B is a sequence of $M$ “easts” and $N$ “norths” in some order. In the example above, $M=4$ and $N=3$. The solution I traced is:
\[
\{\text{east, east, north, north, east, north, east}\}
\]Here is another way to think about the problem: out of the $M+N$ decisions we must sequentially make (moving east or moving north), which $M$ of them will be “east”? The answer is the binomial coefficient!
$\displaystyle
\text{Ways to work} = \binom{M+N}{M} = \frac{(M+N)!}{M!\cdot N!}
$
To answer the specific problem posed with $M=5$ and $N=10$, the number of different paths from $A$ to $B$ is $3003$.
