Mathematics question regarding number of possible route choices for a destination?

Question

Suppose you have a gridded network of streets, with ten streets running east-west intersecting with ten streets running north-south. A 10x10 grid of streets. Assume all the streets permit two-way traffic flow.

The question is this: How many different possible route choices are there if you are in one corner of the grid (southwest corner, for example) and wish to travel to the opposite (northeast) corner?

Another important assumption... assume that you may NOT retrace your steps. My "best answer" choice will go to the one who not only gets it right, but explains, in easy to understand language, HOW you came up with the answer. THANK YOU!

Thank you for that great answer! You're obviously quite smart. To answer your question, I simply mean you may not retrace a route segment you have already taken. You may take any route you want, even if a segment temporarily moves you farther away from the destination, as long as you don't go back and take a segment that you have already taken.

Answer 1

When you say "you may not retrace your steps" can you clarify that?

Do you assume that the person is always trying to advance toward the destination? So once I go one block east, I would never go back west, even if it was a different block?

For example, a possible route is to go north for 10 blocks, go east for 1 block, south for 10 blocks, east for 1 block, north for 10 blocks, etc. It would seem this would sort of count as "retracing" so I want to make sure.

If it is finding the number of ways assuming you can only go north and east, then we can find an answer relatively easily. If you are allowed to meander all over the map, but just not cross a prior path, it is much more difficult to answer...

Assuming it is the former case, you can solve this using Pascal's triangle.

Place a 1 at your starting point (there is only one way to get there)
Now put a 1 at a spot 1 block north, and a 1 at a spot 1 block east. (Again, there is only one way to get to each of these points if we always want to advance).
The next spots are 2 blocks north (1 way), 1 block north-east (2 ways), 2 blocks east (1 way).

Notice how the pattern corresponds to Pascal's triangle turned on its side with each intersection being the sum of the ways to get to the prior corners:
1
1 ..7
1 ..6 21
1 ..5 15 35
1 ..4 10 20 35
1 ..3 ..6 10 15 21
1 ..2 ..3 ..4 ..5 ..6 ..7
1 ..1 ..1 ..1 ..1 ..1 ..1 ..1

Rather than filling out the whole grid, it helps to remember that each spot in Pascal's triangle is related to "n choose k" which can also be written C(n, k).

C(0, 0) = 1
C(1, 0) = 1, C(1, 1) = 1
C(2, 0) = 1, C(2, 1) = 2, C(2, 2) = 1
C(3, 0) = 1, C(3, 1) = 3, C(3, 2) = 3, C(3, 3) = 1
etc.

So the grid looks like:
...
C(5,5) ...
C(4,4) C(5,4) ...
C(3,3) C(4,3) C(5,3) ...
C(2,2) C(3,2) C(4,2) C(5,2) ...
C(1,1) C(2,1) C(3,1) C(4,1) C(5,1) ...
C(0,0) C(1,0) C(2,0) C(3,0) C(4,0) C(5,0) ...

Look along the diagonal:
Block 1: C(0,0)
Block 2: C(2,1)
Block 3: C(4,2)
Block 4: C(6,3)
Block 5: C(8,4)
...
Block 9: C(16,8)
Block 10: C(18,9)

So the value corresponding to our destination corner will be C(18,9)

The formula for "n choose k" is:
C(n, k) = n! / (n-k)! k!

Plugging in our values of n = 18, k = 9:
C(18, 9) = 18! / (18-9)! 9!

If you don't have a calculator or other way to figure this out, you can do this manually, just cancel out factors as you go:
C(18, 9) = (18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10) / (9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1)
C(18, 9) = (2 x 17 x 2 x 15 x 2 x 13 x 2 x 11 x 2) / (4 x 3 x 2 x 1)
C(18, 9) = 17 x 5 x 13 x 2 x 11 x 2
C(18, 9) = 48,620 ways

You could also use Google Calculator by typing '18 choose 9' into the search box.

The answer is there are 48,620 ways assuming you always make progress to the destination and never backtrack or sidetrack.