## A lattice path puzzle

This past week’s Riddler puzzle on FiveThirtyEight asks for the number of different paths of minimum length from a starting intersection of city streets to a destination $m$ blocks east and $n$ blocks north. Put another way, moving on the 2D integer lattice graph, how many paths are there from the origin $(0,0)$ to vertex $(m,n)$ that are of minimum length?

Constraining the paths to minimum length greatly simplifies the problem. So let’s generalize, and instead ask for the number of paths from $(0,0)$ to $(m,n)$ of length $k$— so that the original problem asks for the particular case $k=|m|+|n|$, but what if we allow longer paths where we sometimes move in the “wrong” direction away from the destination?

I think this is a nice problem, with an elegant solution only slightly more complex than the original posed in the Riddler column. As a hint, the animation below visualizes the result, where the path length $k$ increases with each frame, showing the probability distribution of the endpoint of a 2D random walk.

Probability distribution of endpoint of 2D lattice random walk, vs. number of steps.

Perhaps as another hint, note the checkerboard pattern to the distribution; only “half” of the vertices are reachable for a particular path length $k$, and which half is reachable alternates as $k$ increases.

This entry was posted in Uncategorized. Bookmark the permalink.

This site uses Akismet to reduce spam. Learn how your comment data is processed.