Problem 11 · 2014 AMC 8
Medium
Counting & Probability
lattice-pathscomplementary-counting
Jack wants to bike from his house to Jill's house, which is located three blocks east and two blocks north of Jack's house. After biking each block, Jack can continue either east or north, but he needs to avoid a dangerous intersection one block east and one block north of his house. In how many ways can he reach Jill's house by biking a total of five blocks?
Show answer
Answer: A — 4 ways.
Show hints
Hint 1 of 2
Forbidding a point is hard to count head-on, so flip it: count all paths, then throw away the bad ones. (Count what you don't want — complementary counting.)
Still stuck? Show hint 2 →
Hint 2 of 2
A path through (1,1) splits into two independent legs: ways to reach (1,1) times ways to continue from (1,1) to the goal. Multiply them.
Show solution
Approach: total − paths through (1,1)
- Total E/N paths to (3,2): choose which 2 of the 5 steps are North, C(5, 2) = 10.
- Paths that hit the bad corner (1,1): (ways to reach (1,1)) × (ways from (1,1) to (3,2)) = C(2,1) × C(3,1) = 2 × 3 = 6. Multiplying works because the two legs are independent.
- Allowed = total − bad = 10 − 6 = 4.
- Why this transfers: "must avoid X" almost always means "all paths minus paths through X," and any path through a checkpoint factors into (reach it) × (leave it).
Another way — case split on first two moves:
- To avoid (1,1) Jack's first two moves must be either EE or NN.
- After EE he is at (2, 0) and needs 1 E + 2 N in some order: C(3,1) = 3 paths. After NN he is at (0, 2) and needs 3 E + 0 N: 1 path.
- Total: 3 + 1 = 4.
Mark:
· log in to save