Consider the grid shown below; one can imagine that it is a map of roads in a ci
ID: 3020510 • Letter: C
Question
Consider the grid shown below; one can imagine that it is a map of roads in a city. In this problem we consider the problem of moving from one corner of the grid to another.
(a) Suppose that, starting at the point labeled A, you can go one step up or one step to the right at each move, as long as you stay on the grid. If you end up at the point labeled B, how many different paths are there?
(b) Now suppose that we must go through the point labeled C. How many paths are there? If we must instead avoid the point labeled C how many paths are there?
Explanation / Answer
This is a 3X6 grid. The number of different paths from A to B using the condition to move either up or right
is = 9!/(3!*6!)=84
b) The number of paths to reach the point C ( this is a 2X2 grid) is 4!/(2!*21) =6
The number of paths to reach point B from Point C ( grid 1X4 ) is 5!/(1!*4!) = 5
The total number of paths through C are = 6*5 =30
Without using Path C, 84-30 = 54