Question

Suppose you have a wire mesh which is N by M units long, made up of unit square with wire at the edges. (So there are N+1 parallel wires all M long and, perpendicular to these, M+1 all N long).An ant starts off at the bottom left corner of this grid (co-ordinates (0,0) and crawls on the wires the shortest possible distance to reach the top-right corner (N,M). How long is the shortest route. How many different shortest routes are there? (Namely, find a formula in terms of N and M) You might want to try this for small values of N and M and see if you can work out how the number for (N,M) relates to those for (N,M-1) and (N-1,M) If you build up a table of these numbers you might recognise them from elsewhere in mathematics so that might help you find the formula, but you also try to explain the connection.

Answer 1

Answer on question 38563 – Math – Algorithms

One of the way is

To get to the point $(\mathsf{N};\mathsf{M})$ from the point $(0;0)$ , we have to go at least $\mathsf{N}$ units to the right and $\mathsf{M}$ units up. If we go exactly $\mathsf{N}$ steps to the right and $\mathsf{M}$ steps up we get the shortest route and it is equal to $\mathsf{M} + \mathsf{N}$ .

About the second question: How many different shortest routes are there?

We have to do N steps to the right and other up. How many different combinations to do this? It is equal to the number of ways to place the N steps to the right into $\mathsf{N} + \mathsf{M}$ places. And it is equal to

$$A _ {N + M} ^ {N} = A _ {N + M} ^ {M} = (N + M) (N + M - 1) \dots (M + 1).$$

Answer: $\mathsf{N} + \mathsf{M}$ ; $(N + M)(N + M - 1) \ldots (M + 1)$ .