AMC 10 · 2019 · #10
Easy mode Grade 5The map below shows 12 cities drawn as dots, in 3 rows of 4. Each dot is joined by a road to the dots right next to it — left, right, up, and down. There are 17 roads in all. City A is the dot at the top left, and city L is the dot at the bottom right.
Paula drives from A to L. She must drive along exactly 13 of the roads. She may never drive on any part of a road twice, but she may pass through the same city more than once.
How many different routes can Paula drive?
Pick an answer.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: A map shows $12$ cities set out as a grid of $3$ rows and $4$ columns of dots, with $17$ roads joining each dot to the dots directly beside it (left-right and up-down). City $A$ is the top-left dot and city $L$ is the bottom-right dot. Paula starts at $A$, finishes at $L$, and drives along exactly $13$ of the roads, never driving any piece of a road twice. She may pass through the same city more than once. Count how many different routes she can drive.
Givens: $12$ cities in a $3$-row by $4$-column grid, joined by $17$ roads ($9$ horizontal and $8$ vertical); The route starts at $A$ (top-left dot) and ends at $L$ (bottom-right dot); Exactly $13$ roads are driven, so exactly $17 - 13 = 4$ roads are skipped; No road, or part of a road, may be driven twice; cities may be visited more than once; Choices: (A) $0$, (B) $1$, (C) $2$, (D) $3$, (E) $4$
Unknowns: The number of different $13$-road routes from $A$ to $L$
Understand
Restated: A map shows $12$ cities set out as a grid of $3$ rows and $4$ columns of dots, with $17$ roads joining each dot to the dots directly beside it (left-right and up-down). City $A$ is the top-left dot and city $L$ is the bottom-right dot. Paula starts at $A$, finishes at $L$, and drives along exactly $13$ of the roads, never driving any piece of a road twice. She may pass through the same city more than once. Count how many different routes she can drive.
Givens: $12$ cities in a $3$-row by $4$-column grid, joined by $17$ roads ($9$ horizontal and $8$ vertical); The route starts at $A$ (top-left dot) and ends at $L$ (bottom-right dot); Exactly $13$ roads are driven, so exactly $17 - 13 = 4$ roads are skipped; No road, or part of a road, may be driven twice; cities may be visited more than once; Choices: (A) $0$, (B) $1$, (C) $2$, (D) $3$, (E) $4$
Plan
Primary tool: #14 Extreme Principle
Secondary: #1 Draw a Diagram, #3 Eliminate Possibilities, #2 Make a Systematic List
Tool #14 (Extreme Principle) is the crux: work out the largest number of times each city could possibly be used, add those maxima up, and compare with the number of stops $13$ roads demand. The two totals turn out to be equal, so nothing is spare and every city must be used at its maximum. Tool #1 (Diagram) supplies the coordinates and road-counts that the maximum depends on. Tool #3 (Eliminate Possibilities) then kills the wrong first move and pins down which four roads are skipped. Tool #2 (Systematic List) finishes by counting the only free choices left.
Execute — Answer: E
5.G.A.1 Step 1 Put coordinates on the map
- Name each city $(x,y)$ with $x = 0,1,2,3$ running left to right and $y = 0,1,2$ running bottom to top.
- Then $A = (0,2)$ and $L = (3,0)$.
- Two cities are joined exactly when they differ by $1$ in one coordinate and agree in the other, so there are $3 \cdot 3 = 9$ horizontal roads and $4 \cdot 2 = 8$ vertical roads.
- That is $17$ roads, matching the problem.
💡 Coordinates give every city a name, so "the city next to that one" stops being guesswork.
4.G.A.1 Step 2 Count the roads at each city
- Count how many roads meet each city.
- The four corners $A = (0,2)$, $(3,2)$, $(0,0)$, $L = (3,0)$ have $2$ roads each.
- The six cities on an edge but not at a corner — $(1,2)$, $(2,2)$, $(1,0)$, $(2,0)$, $(0,1)$, $(3,1)$ — have $3$ each.
- The two middle cities $(1,1)$ and $(2,1)$ have $4$ each.
- Check the total: every road gets counted at both of its ends, so the road-counts should add to twice $17$.
💡 Adding up road-counts counts every road twice, which is a free check that none was missed.
4.NBT.B.6 Step 3 How often can one city be used?
- Passing through a city burns two roads there, one in and one out, and no road may be reused.
- So a city with $d$ roads can be passed through at most $\left\lfloor \frac{d}{2} \right\rfloor$ times: $d = 2$ allows $1$, $d = 3$ allows $1$ with the third road stranded, and $d = 4$ allows $2$.
- The two endpoints work differently.
- Leaving $A$ costs $1$ road, and coming back to $A$ and setting off again would cost $2$ more — that is $3$ roads at a city with only $2$.
- So $A$ is used exactly once, and the same count gives $L$ exactly once.
💡 Roads at a city are spent in in-out pairs, so an odd road-count always strands one road.
4.OA.A.3 Step 4 The budget is exactly full
- Driving $13$ roads means making $14$ stops, counting a return visit as its own stop.
- One stop is $A$ and one is $L$, so $12$ stops are spread over the other $10$ cities.
- Their limits from the previous step add to $2 \cdot 1 + 6 \cdot 1 + 2 \cdot 2 = 12$ — exactly the $12$ needed.
- Nothing is spare, so every one of those cities is used the maximum number of times: $(1,1)$ and $(2,1)$ are each passed through twice with all $4$ of their roads driven, the corners $(0,0)$ and $(3,2)$ are each passed through once with both roads driven, and each of the six $3$-road cities is passed through once with exactly one of its roads skipped.
💡 When the most you could do equals the least you must do, every choice is already decided.
2.OA.C.3 Step 5 Locate the four skipped roads
- Count skipped road-ends.
- $A$ skips $1$ of its $2$ roads, $L$ skips $1$, and each of the six $3$-road cities skips $1$, giving $8$ skipped road-ends.
- On the other side, $17 - 13 = 4$ roads are skipped and each has $2$ ends, giving $4 \cdot 2 = 8$ as well.
- The two counts agree exactly, so every skipped road must join two cities from that list of eight.
- In particular no skipped road may touch $(0,0)$, $(3,2)$, $(1,1)$ or $(2,1)$.
💡 Counting the same skipped ends two ways — by city and by road — leaves no room for a stray skipped road.
4.G.A.1 Step 6 Paula cannot start downward
- Suppose the first road is $A \to (0,1)$.
- City $(0,1)$ has $3$ roads and is passed through only once, so it drives exactly $2$ of them: the road from $A$ plus one more.
- But the corner $(0,0)$ must drive both of its roads, which forces the road $(0,1)\!-\!(0,0)$, and the middle city $(1,1)$ must drive all four of its roads, which forces $(0,1)\!-\!(1,1)$.
- That would be $3$ driven roads at $(0,1)$, one too many.
- So the first road is $A \to (1,2)$, and $A\!-\!(0,1)$ is one of the four skipped roads.
💡 A city that can be entered only once cannot satisfy three separate demands.
4.G.A.1 Step 7 Every remaining road is forced
- Turning the map $180^\circ$ swaps $A$ with $L$ and leaves the road pattern unchanged, so the same argument at the far end skips $(3,1)\!-\!L$ and makes the final road $(2,0) \to L$.
- Now $(1,2)$ is entered from $A$ and must also supply $(1,1)$ with its fourth road, so the road $(1,2)\!-\!(2,2)$ is skipped; the mirrored statement skips $(1,0)\!-\!(2,0)$.
- That names four skipped roads, and the budget was exactly four, so every other road is driven.
- The set of $13$ driven roads is therefore unique.
💡 Once four skipped roads are named the budget is spent, so nothing else may be skipped.
4.G.A.1 Step 8 Read the shape of the route
- Those $13$ roads form one chain with two square loops hanging on it.
- From $A$ go $A \to (1,2) \to (1,1)$.
- Then drive the four roads of the lower-left square $(1,1), (0,1), (0,0), (1,0)$, which brings you back to $(1,1)$.
- Then take $(1,1) \to (2,1)$.
- Then drive the four roads of the upper-right square $(2,1), (2,2), (3,2), (3,1)$, which brings you back to $(2,1)$.
- Then finish $(2,1) \to (2,0) \to L$.
💡 The two twice-visited cities are exactly the spots where the route ties a loop and comes back.
3.OA.A.1 Step 9 Count the ways to turn
- The route is now fixed except for one free choice at each loop: the lower-left square may be driven clockwise or counterclockwise, and so may the upper-right square.
- The two choices do not affect each other, so the number of routes is $2 \cdot 2 = 4$, which is choice $\textbf{(E)}$.
💡 Two independent two-way choices multiply, they do not add.
5.G.A.1 Name each city $(x,y)$ with $x = 0,1,2,3$ running left to right and $y = 0,1,2$ 4.G.A.1 Count how many roads meet each city. The four corners $A = (0,2)$, $(3,2)$, $(0, 4.NBT.B.6 Passing through a city burns two roads there, one in and one out, and no road ma 4.OA.A.3 Driving $13$ roads means making $14$ stops, counting a return visit as its own s 2.OA.C.3 Count skipped road-ends. $A$ skips $1$ of its $2$ roads, $L$ skips $1$, and each 4.G.A.1 Suppose the first road is $A \to (0,1)$. City $(0,1)$ has $3$ roads and is passe 4.G.A.1 Turning the map $180^\circ$ swaps $A$ with $L$ and leaves the road pattern uncha 4.G.A.1 Those $13$ roads form one chain with two square loops hanging on it. From $A$ go 3.OA.A.1 The route is now fixed except for one free choice at each loop: the lower-left s Review
Reasonableness: Trace one route to confirm it really exists: $A(0,2) \to (1,2) \to (1,1) \to (1,0) \to (0,0) \to (0,1) \to (1,1) \to (2,1) \to (3,1) \to (3,2) \to (2,2) \to (2,1) \to (2,0) \to L(3,0)$. That is $13$ roads with none repeated, so choice (A) $0$ is out. Reversing just one loop gives a genuinely different route, so the two loops contribute $2 \cdot 2 = 4$, not $2$ — choice (C) is what you get by noticing only one of the two loops. No more than $4$ is possible either, because the set of driven roads was forced before any turning choice was made. The skipped-road picture is consistent too: the four skipped roads are pairwise disjoint and use up exactly the eight road-ends that had to be skipped.
Alternative: Tool #2 (Make a Systematic List): skip the capacity count and search by hand with pruning. From $A$ there are only $2$ first moves, and the rule "a city with $3$ roads can be entered only once" kills branches within a few steps — the downward start dies immediately at $(0,1)$, and the rightward start quickly forces the two square loops. A tidy cross-check on the finish: in the forced set of $13$ driven roads, only $A$ and $L$ have an odd number of driven roads, which is exactly the condition for a route that uses every one of those roads from $A$ to $L$; counting such routes gives $2 \cdot 2 = 4$ again.
CCSS standards used (min grade 5)
2.OA.C.3Determine whether a group of objects has an odd or even number (Seeing that a city with an odd road-count must strand one road, and matching the $8$ skipped road-ends to $4$ skipped roads.)3.OA.A.1Interpret products of whole numbers as total number of objects in groups (Multiplying the two independent loop directions to get $2 \cdot 2 = 4$ routes.)4.G.A.1Draw points, lines, line segments, rays, angles, and identify in figures (Reading the map as dots and segments, counting the roads at each city, and tracking which segments are driven.)4.NBT.B.6Find whole-number quotients and remainders with up to four-digit dividends (Turning a city's road-count $d$ into its visit limit $\left\lfloor \frac{d}{2} \right\rfloor$.)4.OA.A.3Solve multi-step word problems using four operations with whole numbers (Converting $13$ roads into $14$ stops, then $12$ stops for the other cities, and comparing with the total limit $12$.)5.G.A.1Use a pair of perpendicular number lines forming a coordinate system (Naming the $12$ cities as grid points $(x,y)$ so each road can be identified precisely.)
⭐ This AMC 12 problem needs only Grade 5 tools: count how many times each city could possibly be used, notice that total is exactly the number of stops $13$ roads require, and the whole route is forced — only the two square loops can still be turned either way, giving $2 \cdot 2 = 4$, choice $\textbf{(E)}$.
⭐ This AMC 12 problem needs only Grade 5 tools: count how many times each city could possibly be used, notice that total is exactly the number of stops $13$ roads require, and the whole route is forced — only the two square loops can still be turned either way, giving $2 \cdot 2 = 4$, choice $\textbf{(E)}$.
More like this
Same archetype — closest grade level first.