How many ways home?
Tonight's idea
School is at the bottom-left corner of a grid of streets. Home is to the right and up. You only ever walk right or up, never back. How many different routes are there?
Do not try to draw them all. Instead, write at every corner the number of routes that reach it.
Along the bottom street there is one route to each corner: keep going right. Up the left street there is one route too.
Now take any other corner. Your last step came either from the left or from below. So add those two numbers.
Routes to a corner = routes to the corner on its left + routes to the corner below it.
Fill in the grid row by row. Each sum is small, and the number at home is the answer. Here there are 10 ways home.
Watch one: a closed corner
Home is 3 blocks right and 3 blocks up. Roadworks close one corner. No route may pass through it, so it gets a 0.
Fill in the rest with the same rule. Home gets 8.
With no roadworks the same grid gives 20. So 12 of the 20 routes used that one corner.
Tap any corner to see its number and the two numbers it comes from: mathdetours.com/demos/gridpaths.html.
Your turn
- Fill in Grid 1. How many routes are there? Write each one as a string of R (right) and U (up), like RRUU.
- Fill in Grid 2. (a) How many routes are there? (b) How many blocks long is every route?
- Fill in Grid 3. (a) How many routes are there? (b) Some numbers appear twice. Which ones, and why?
- Home is 4 blocks right and 4 blocks up, and there are 70 routes. The sweet shop is 2 right and 2 up from school. (a) How many routes pass the shop? Hint: count school to shop, then shop to home. (b) How many miss it?
Stretch: add the diagonals
In Grid 3, add up the numbers on each slanting line of corners: the 1 at school, then 1 + 1, then 1 + 2 + 1, then the next line. What happens to the totals each time? Explain why.
Answers
- Rows from the bottom: 1 1 1, then 1 2 3, then 1 3 6. There are 6 routes: RRUU, RURU, RUUR, URRU, URUR, UURR.
- Rows from the bottom: 1 1 1 1 1, then 1 2 3 4 5, then 1 3 6 10 15. (a) 15 routes. (b) Every route is 6 blocks: 4 right and 2 up, in some order.
- Rows from the bottom: 1 1 1 1, then 1 2 3 4, then 1 3 6 10, then 1 4 10 20. (a) 20 routes. (b) 3, 4 and 10 each appear twice (and there are lots of 1s). Swap "right" and "up" and the grid looks the same, so the numbers match across the slanting line from school to home.
- (a) School to shop is Grid 1: 6 routes. Shop to home is also 2 right and 2 up: 6 routes. Each first half can join each second half, so \(6 \times 6 = 36\) routes pass the shop. (b) \(70 - 36 = 34\).
Stretch. The totals are 1, 2, 4, 8. They double. Each slanting line holds the corners you can reach in the same number of steps. At every step you choose right or up, so each extra step doubles the number of walks. These slanting lines are the rows of Pascal's triangle, which is on a grade 6 sheet.