Question

Cities $A,$ $B,$ $C,$ $D,$ and $E$ are connected by roads $AB,$ $AD,$ $AE,$ $BC,$ $BD,$ $CD,$ and $DE.$ How many different routes are there from $A$ to $B$ that use each road exactly once? (Such a route will necessarily visit some cities more than once.)

$7$

$9$

$12$

$16$

$18$

Answer: D

Concepts:graph theory casework multiplication principle

Difficulty rating: 1670

Solution:

City $E$ (roads $AE, DE$ ) is a detour on an $A$ – $D$ trip, and city $C$ (roads $BC, CD$ ) is a detour on a $B$ – $D$ trip. Replace them to get a graph on $A, B, D$ with two $A$ – $D$ connections, two $B$ – $D$ connections, and one $A$ – $B$ road. The trails from $A$ to $B$ using each once are of $4$ types: $ABDADB,$ $ADABDB,$ $ADBADB,$ and $ADBDAB.$ Each detour (through $E,$ through $C$ ) can be taken on either passage, so each type gives $4$ actual routes, for $4\cdot 4 = 16$ routes. Thus, the correct answer is D.

2013 AMC 12B Problem 12

Answer: D

Difficulty rating: 1670

Solution:

Problem 12 in Other Years