Corner-to-corner routes on a square grid

Question

On a square street grid you walk from the bottom-left corner to the top-right corner, going 3 blocks east and 3 blocks north, moving only east or north. How many different shortest routes are there?

Accepted Answer

A route is a string of 3 east-steps and 3 north-steps, 6 steps total. Choose which 3 of the 6 slots are north-steps: \binom{6}{3} = \frac{6 	imes 5 	imes 4}{3 	imes 2 	imes 1} = 20. Because east and north counts are equal here, the choice is perfectly symmetric: \binom{6}{3} = \binom{6}{3}. Takeaway. A square k 	imes k grid has \binom{2k}{k} shortest routes. For k=3 that is \binom{6}{3} = 20.

Corner-to-corner routes on a square grid

Your answer

Discussion

Learn the concepts

Related questions