Try each problem before reading the solutions. Write down the step that makes your argument complete.
Problems
1. How many shortest grid paths lead from (0, 0) to (4, 3), using only right and up steps?
2. How many of those paths avoid (2, 1)?
3. Now forbid both (2, 1) and (3, 2). How many shortest paths remain?
Solutions
1. There are 35 paths. Choose the positions of the three up steps among seven steps.
2. There are 17. Exactly 3 × 6 = 18 paths pass through (2, 1), counting the independent segments before and after it. Subtract 18 from 35.
3. There are 9. There are 18 paths through (2, 1), 10 × 2 = 20 through (3, 2), and 3 × 2 × 2 = 12 through both. The answer is 35 − 18 − 20 + 12.
Leave a Reply