Question

La figura de abajo es un mapa que muestra $12$ ciudades y $17$ caminos que conectan ciertos pares de ciudades. Paula desea recorrer exactamente $13$ de esos caminos, comenzando en la ciudad $A$ y terminando en la ciudad $L,$ sin recorrer ninguna parte de un camino más de una vez. (Paula puede visitar una ciudad más de una vez.) ¿Cuántas rutas diferentes puede tomar Paula?

The figure below is a map showing $12$ cities and $17$ roads connecting certain pairs of cities. Paula wishes to travel along exactly $13$ of those roads, starting at city $A$ and ending at city $L,$ without traveling along any portion of a road more than once. (Paula is allowed to visit a city more than once.) How many different routes can Paula take?

$0$

$1$

$2$

$3$

$4$

Solución:

Una ruta usa $13$ caminos como un recorrido abierto de $A$ a $L,$ así que en los caminos usados exactamente $A$ y $L$ tienen grado impar y toda otra ciudad tiene grado par.

En el mapa completo las ciudades de las esquinas $A$ y $L$ ya tienen grado par $2,$ y seis ciudades de los bordes tienen grado impar $3.$ Eliminar $4$ caminos debe cambiar la paridad de $A,$ $L,$ y de esas seis ciudades, y de ninguna otra. Esto obliga a que los cuatro caminos eliminados emparejen esas ocho ciudades de la única manera posible, así que el conjunto de $13$ caminos usados queda determinado de forma única.

Contar los recorridos eulerianos de $A$ a $L$ en ese grafo da exactamente $4$ rutas.

Por lo tanto, E es la respuesta correcta.

A route uses $13$ roads as an open trail from $A$ to $L,$ so on the used roads exactly $A$ and $L$ have odd degree and every other city has even degree.

In the full map the corner cities $A$ and $L$ already have even degree $2,$ and six edge-cities have odd degree $3.$ Removing $4$ roads must flip the parity of $A,$ $L,$ and those six cities, and of no others. This forces the four removed roads to pair up those eight cities in the only possible way, so the set of $13$ used roads is uniquely determined.

Counting the Eulerian trails from $A$ to $L$ on that graph gives exactly $4$ routes.

Thus, E is the correct answer.

2019 AMC 12B Problema 10

Solución:

El Problema 10 en otros años