A secretary works in a building located nine blocks east and eight blocks north of his home. Every day he walks 17 blocks to work. The map is a 9 x 8 and each block is a square of the same size.
1) How many different routes are possible for him? $\binom{17}{9}$
2) How many different routes are possible if the one block in the easterly direction, whic begins four blocks east and three blocks north of his home, is under water (and he can't swim) (Hint: Count the routes that use the block under water)
I solved the first one on my own. Can anyone help me with the second question?
Best Answer
Well, the assumption is he only travels north and east and never west and south.. this should be made clear.
Hint: Now, if the block is under water, presumably he cannot use any of the streets around the block. Let us say the block is the square with vertices $(m,n)$, $(m+1,n)$, $(m, n+1)$, $(m+1, n+1)$.
Then, the number of routes that include a street near the block are those that pass through $(m,n)$ plus those that pass through $(m+1, n)$ and dont pass through $(m,n)$ plus those that pass through $(m, n+1)$ and dont pass through $(m,n)$..
[Note that any route that passes through $(m+1,n+1)$ must also pass through some other vertex, so you dont need to count these].
Can you solve it now?