2013 AMC 12B Problem 12

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

B

that use each road exactly once? (Such a route will necessarily visit some cities more than once.)

Show solution

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

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.

Tagged: graph theory · casework · multiplication principle