Grid routes that pass a coffee shop

Question

You walk a grid from home to work, going $5$ blocks east and $3$ blocks north (only east or north moves). A coffee shop sits at the corner that is $2$ blocks east and $1$ block north of home, and you want a shortest route that passes it.

How many shortest routes pass through the coffee shop?

Accepted Answer

Split the trip into two independent legs at the coffee shop and multiply the route counts. Leg 1, home to coffee shop (2 east, 1 north): that is 3 steps, choose the 1 north-step, \binom{3}{1} = 3 routes. Leg 2, coffee shop to work: you have 5 - 2 = 3 east and 3 - 1 = 2 north blocks left, 5 steps, choose the 2 north-steps, \binom{5}{2} = 10 routes. Since any first-leg route can pair with any second-leg route, multiply: 3 	imes 10 = 30. Takeaway. To force a route through a checkpoint, count routes to it times routes from it, then multiply. Here \binom{3}{1}\binom{5}{2} = 30.

Grid routes that pass a coffee shop

Your answer

Discussion

Learn the concepts

Related questions