Paths to Work

My house is close to the corner of 15th and High in Topeka, KS.  My office is close to Boswell (5 blocks east of High) and 17th (2 blocks south).  How many paths can I take if I choose only to travel south or east (and not north or west, which would be counterproductive)?

This is a small enough problem that you could literally count up the number of paths pretty easily. In fact, why don’t you try that out and see if you get the correct answer!

Now, what if you were faced with counting up the paths for this situation?

HomeWorkMap2

Would you want to count up the number of the paths to work in the same way? Instead, let’s find a pattern that we can work with and understand, and then apply that to any grid of any width and length.

Let’s go back to the original 5×2 grid and analyze why there are 21 total paths.  It’s easier to start at the end and work backward. Notice that in the 5×2 grid that there are 18 different “corners” that we could potentially find ourselves.  To go from home to work, we must go east 5 times and south twice in some order.

What if we find ourselves 5 blocks east and one block south, or 4 blocks east and 2 blocks south? According to the diagram below, we only have 1 option in each of those cases.  We must travel the final south path in the first case, or the final east path in the second.

Map01

Now, if we look at the corner diagonal from work (this would be 4 blocks east and 1 block south), you’ll notice that we have an option of going south or east from here. If we choose east there is only 1 option, and if we choose south, there is only one option. Adding the two together, we get 2 paths from this corner.

Now, let’s expand out a single block.

Map2

If we find ourselves 5 blocks east, then we have only one path choice, and that is to travel south two blocks to work.  If we find ourselves 2 blocks south and 3 blocks east, again, we have only one path option, and that is to travel the two more blocks east to work.

Now, the fun part. When we look at the corner that is 4 blocks east, we have the option of traveling south or east.  South will give us 2 paths to choose from, and east will give us only 1 path to choose, for a total of 3 paths from that corner.

If we are at the corner that is 3 blocks east and 1 block south, we again have the option of traveling south to a corner that has only 1 choice and east to a corner with 2 choices for a total of 3 paths from that corner.

Finally, at the corner that is 3 blocks east, we can travel south to a corner that has 3 paths to choose from, or east to a corner with 3 paths to choose from, giving us a total of 6 paths to follow.

Let’s fill out our original map, to detect any patterns.

HomeWorkMap

If you placed “Work” at the top of a triangle it might begin to look like the triangle I talked about in The Yanghui Triangle, Part I or  The Yanghui Triangle, Part II. Indeed, we can find the number of paths using combinations.

Previously, I described how to get from home to work we must pass 7 corners.  Each of the 7 corners must have a decision to go south or east, but there must be exactly 5 corners in which we choose to go east and 2 corners in which we decide to go south.

With 7 corners, how many ways can we choose 2 of them in which to go east (and therefore south on the other 5)?  The answer is \binom{7}{2} = 21=\binom{7}{5}.  This can be found using the {}_nC_r button on your calculator. First, push 7, then use the {}_nC_r button, then push 2 (or 5), and then press enter.

We now have the tools to answer the bigger 6×10 grid puzzle.  If our work is 6 blocks south and 10 blocks east, we will need to visit 16 corners on our path to work.  Of these 16 corners, we will need to decide which of the 6 we will travel south on (and, therefore, which 10 we travel east on).  This is \binom{16}{6} or {}_{16}C_{6}, which is 8008.  This would have taken a little longer if we counted the paths directly.

 

 

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s