Question

Las ciudades $A,$ $B,$ $C,$ $D,$ y $E$ están conectadas por los caminos $AB,$ $AD,$ $AE,$ $BC,$ $BD,$ $CD,$ y $DE.$ ¿Cuántas rutas diferentes hay desde $A$ hasta $B$ que usan cada camino exactamente una vez? (Tal ruta necesariamente visitará algunas ciudades más de una vez.)

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$

Respuesta: D

Conceptos:teoría de grafos análisis por casos principio de multiplicación

Nivel de dificultad: 1670

Pista pequeña:

Las ciudades $C$ y $E$ tocan cada una solo dos caminos, así que se comportan como desvíos en las conexiones $A$ - $D$ y $B$ - $D$ .

Cities $C$ and $E$ each touch only two roads, so they behave like detours on the $A$ – $D$ and $B$ – $D$ connections

Pista grande:

Cuenta los recorridos desde $A$ hasta $B$ en el grafo reducido, luego multiplica por las opciones independientes de desvío.

Count the trails from $A$ to $B$ on the reduced graph, then multiply by the independent detour choices

Solución:

La ciudad $E$ (caminos $AE, DE$ ) es un desvío en un trayecto $A$ - $D$ , y la ciudad $C$ (caminos $BC, CD$ ) es un desvío en un trayecto $B$ - $D$ . Al reemplazarlas se obtiene un grafo sobre $A, B, D$ con dos conexiones $A$ - $D$ , dos conexiones $B$ - $D$ , y un camino $A$ - $B$ . Los recorridos desde $A$ hasta $B$ que usan cada uno una vez son de $4$ tipos: $ABDADB,$ $ADABDB,$ $ADBADB,$ y $ADBDAB.$ Cada desvío (por $E,$ por $C$ ) puede tomarse en cualquiera de los dos pasos, así que cada tipo da $4$ rutas reales, para $4\cdot 4 = 16$ rutas. Por lo tanto, la respuesta correcta es D.

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 Problema 12

Respuesta: D

Nivel de dificultad: 1670

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años