Problem 9 · 1986 AJHSME
Medium
Counting & Probability
count-pathsdirected-graph
Show answer
Answer: E — 6.
Show hints
Hint 1 of 3
Tracing every full route by hand invites missed ones and double-counts. Notice something cleaner: the number of ways to reach a point is just the total of the ways to reach the points whose arrows feed into it.
Still stuck? Show hint 2 →
Hint 2 of 3
So label each point with a count, working outward from M (which counts as 1 way — you're already there), adding up the incoming arrows' counts as you go.
Still stuck? Show hint 3 →
Hint 3 of 3
Follow the arrows in order so every point you add up is already finished. Any point an arrow leaves *to* gets that count poured into it.
Show solution
Approach: label each point with its number of routes (build up from M)
- The key idea: the number of routes into a point equals the sum of the routes into the points that arrow toward it. So you never trace a whole path — you just accumulate. Start: M = 1 (there's one way to 'be at the start').
- Top region: B is fed only by M, so B = 1. A is fed by M and by B, so A = 1 + 1 = 2.
- Bottom: D is fed only by A, so D = 2. C is fed by A, B, and D, so C = 2 + 1 + 2 = 5.
- Finally N is fed by B and C: N = 1 + 5 = 6 routes.
- Why this transfers: this 'add up the incoming counts' trick is exactly how you count lattice paths (and how Pascal's triangle is built) — it turns an explosion of routes into a handful of additions.
Mark:
· log in to save