Different Paths

We must travel from A to B along the lines shown. If we only allow movement upward or to the right, how many different paths are there from A to B?
image
Source: NCTM Mathematics Teacher, December 2005

SOLUTION
image
If we fill in the entire 4\times 4 grid including the top left corner, the bottom right corner and the center, a path from A to B would take 4 steps upward and 4 steps to the right. How many different paths from A to B is given by how many ways can we choose 4 steps to the right out of 8 steps?
\dbinom{8}{4}=70
We need to subtract from 70 the number of paths that go through the 3 points in the top left corner, the 3 points of the right bottom corner, and the central point of the grid. With a little patience and a pencil and paper, we find out that 8 paths go through the top left corner; 8 paths through the right bottom corner; 18 paths through the central point from the left hand point C; and 18 paths through the central point from the bottom point D.
image
Number of different paths from A to B equals
70-8-8-18-18=18

Answer: 18

Alternative solution
We collapse the empty central square and thus obtain a 3\times 3 grid as follows
image
A path from A to B would take 6 steps 3 of which are upward and 3 to the right. How many ways can we choose 3 steps to the right out of 6 steps is given by
\dbinom{6}{3}=20
We subtract the paths going through C and D and obtain
20-1-1=18

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , . Bookmark the permalink.

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