Shortest routes across a city grid

Question

A city is laid out as a grid of streets. To walk from your home to the office you must go $4$ blocks east and $3$ blocks north, and to keep it a shortest route you only ever move east or north (never west or south).

How many different shortest routes are there?

Accepted Answer

Every shortest route is a sequence of 4 east-steps (E) and 3 north-steps (N), in some order, for 7 steps total. Each route corresponds to one such string, like EENENEN, and any string with exactly 4 E's and 3 N's is a valid route. So we just need to choose which 3 of the 7 step-slots are the north-steps (the rest are east): \binom{7}{3} = \frac{7 	imes 6 	imes 5}{3 	imes 2 	imes 1} = 35. Choosing the 4 east-steps instead gives the same answer, \binom{7}{4} = 35. Takeaway. Shortest grid routes with a east and b north steps number \binom{a+b}{b}. Here \binom{7}{3} = 35.

Shortest routes across a city grid

Your answer

Discussion

Learn the concepts

Related questions