Of Drunkards

In a city with orthogonal streets and regular city block, a party-goer leaves a bar and walks back home. His home is North East from the bar, N blocks up, and E blocks east. At each intersection, he decide to go either north or east randomly—but whatever’s left of his sobriety keeps from backtracking: he always moves closer to home. How many ways can the drunkard get get back home?

city

So if there’s only one city block to go around, we only have two possibilities:

1x1

Either we go north first, or we go east first. If we have two city blocks, then there’s three choices:

1x2

Then, if we have 2\times{2} city blocks, we have 6 choices:

2x2

The number of path grows rapidly after this.

If you try to solve the problem by enumeration, you probably will end up with a recurrence such as

I(N,E)=\begin{cases}1 & N=0~\mathrm{or}~E=0\\ I(N-1,E)+I(N,E-1)&\mathrm{otherwise}\end{cases},

(ignoring minor parametrization variations depending on whether you count intersections or city block). Solving that recurrence directly is not easily done, but we can make connections with similar recurrences we know. It does look like

\displaystyle\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},

while not being exactly the same.

However, to solve this easily, we’ll have to do some lateral thinking. If rather than taking the problem recursively, as its initial formulation seems to suggest, we take it as an encoding approach to the problem, we can find a much simpler solution. If we encode one of the many paths as a series of one and zeros, then one specific path will be encoded with, say, N 1s, encoding going north, and E zeroes, encoding east. So the question now becomes, how many strings are there with N ones and E zeroes? Or… How many strings of length N+E have N ones? Simply

\displaystyle\binom{N+E}{N},

is the numbers of way of picking N ones amongst N+E objects.

However we have a minor adjustment to make to this formula to make it agree with the recurrence above, I(N,E), because I(N,E) doesn’t count street segments, it counts intersections. Therefore, we have that

\displaystyle I(N,E)=\binom{N+E+1}{N}.

*
* *

Here we have another example where lateral thinking helps. Rather than trying to solve the recurrence directly (with something like characteristic polynomials and whatever other tools you happen to know) we found a perfectly cromulent solution by restating the problem as an encoding problem.

One Response to Of Drunkards

  1. Carl Tessier says:

    I remember implementing this algorithm in the naïve recursive manner many years ago. Trying to solve it for N = E = 20 was obviously a failure, so I modified it to store partial results; the program then ran in a matter of seconds.

    Then I realized that I could (also) solve it even faster using combinatorics (permutations of “go north” and “go east”).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: