AMC12 2013 B

AMC12 2013 B · Q12

AMC12 2013 B · Q12. It mainly tests Basic counting (rules of product/sum), Casework.

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.)

城市A、B、C、D和E通过道路AB、AD、AE、BC、BD、CD和DE连接。从A到B使用每条道路恰好一次的不同路径有多少条？（这样的路径必然会多次访问某些城市。）

(A) 7 7

(B) 9 9

(D) 16 16

(E) 18 18

Answer

Correct choice: (D)

正确答案：（D）

Solution

Answer (D): Cities $C$ and $E$ and the roads leading in and out of them can be replaced by a second $A-D$ road and a second $B-D$ road, respectively. If routes are designated by the list of cities they visit in order, then there are 4 types of routes: $ABDADB$, $ADABDB$, $ADBADB$, and $ADBDAB$. Each type of route represents 4 actual routes, because the trip between $A$ and $D$ can include the detour through $E$ either the first or the second time, and a similar choice applies for the trip between $B$ and $D$. Therefore there are $4 \cdot 4 = 16$ different routes.

答案（D）：城市 $C$ 和 $E$ 以及通往它们并从它们离开的道路，分别可以用第二条 $A-D$ 道路和第二条 $B-D$ 道路来替代。如果把路线用按顺序经过的城市列表来表示，那么共有 4 种路线类型：$ABDADB$、$ADABDB$、$ADBADB$ 和 $ADBDAB$。每种路线类型对应 4 条实际路线，因为在 $A$ 与 $D$ 之间的行程中，绕道经过 $E$ 可以发生在第一次或第二次；同样的选择也适用于 $B$ 与 $D$ 之间的行程。因此共有 $4 \cdot 4 = 16$ 条不同的路线。

Topics