AMC 10 · 2013 · #12
Grade 7 counting
Pick an answer.
Seven roads can be ordered in a great many ways, so listing routes blindly is hopeless. Two ideas shrink the job to something a person can finish by hand and be sure of. First, count road-ends instead of roads: how many road-ends a city has decides how many times a route can stop there, and that pins down the shape of every route before any listing starts. Second, cities C and E each have only two roads, so a route that enters must leave by the other one — these are forced detours carrying no choice, and splicing them out leaves a three-city picture. The splice has to be reversible, otherwise the small picture would be answering a different question, so that reversal gets proved rather than assumed. What survives is a short, provably complete list, and the choices thrown away by the splice are put back by multiplication at the end.
Count the roads at each city
Counting roads per city is the first move.
Every road has two ends, so adding up the roads at all the cities must double-count each road exactly once.
Every road has two ends, so adding up the roads at all the cities counts each road exactly twice.
▸ Why?
Each road belongs to exactly two cities, so summing over cities visits it twice.
▸ Why?
Passing through a city uses roads two at a time, so an odd pile of roads can only sit at a start or a finish.
Odd counts fix where stops can happen
The odd counts fix the start and finish.
Passing through a place always uses roads two at a time, so an odd pile of roads can only belong to a place where the trip begins or ends.
2.OA.C.3Organize Information In More WaysC and E are forced detours
Two-road cities are forced detours.
A city with exactly two roads is a corridor, not a junction — once you walk in there is only one way out.
7.SP.C.8Solve An Easier Related ProblemSplice them out, and check it reverses
Splicing them out leaves a smaller picture.
Shrinking a corridor to a doorway loses no journeys, because you can always stretch the doorway back into the corridor.
4.OA.A.3Draw A DiagramSplit the count into order and twins
The count splits into order times choices.
Deciding the itinerary and deciding which of two identical-looking roads you took are separate decisions, so their counts multiply.
7.SP.C.8Identify SubproblemsList every city order
There are four possible city orders.
Once you know which cities appear how often, the only freedom left is arranging them, and the no-repeat rule kills most arrangements immediately.
7.SP.C.8Make A Systematic ListStretch one order back to a real route
Each stretches back to a real route.
Checking that one shrunken route inflates back into a legal seven-road drive confirms the shortcut was a translation, not a loss.
7.SP.C.8Solve An Easier Related ProblemMultiply the two counts
Multiplying gives 16, choice (E).
A complete list of itineraries times the fixed number of ways to realise each itinerary gives the whole count with nothing missed and nothing repeated.
4.OA.A.3Make A Systematic ListCount the road-ends at each city first: even means you always pass through, odd means the trip must start or end there — and a city with only two roads is a corridor you can shrink away.
- Count the roads at each city
- Odd counts fix where stops can happen
- C and E are forced detours
- Splice them out, and check it reverses
- Split the count into order and twins
- List every city order
- Stretch one order back to a real route
- Multiply the two counts