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$

Respuesta: E

Conceptos:teoría de grafos paridad análisis por casos

Nivel de dificultad: 1640

Pista pequeña:

Usar $13$ de los $17$ caminos deja exactamente $4$ caminos sin usar

Using $13$ of the $17$ roads leaves exactly $4$ roads unused

Pista grande:

Existe un recorrido solo si únicamente $A$ y $L$ tienen grado impar; esto obliga a decidir qué $4$ caminos eliminar

A trail exists only if just $A$ and $L$ have odd degree; this forces which $4$ roads to drop

Solución:

Llamemos a las cuatro ciudades de la fila superior $A,B,C,D,$ a las de la fila central $E,F,G,H,$ y a las de la fila inferior $I,J,K,L.$ Una ruta que usa $13$ caminos es un recorrido euleriano abierto, así que en el grafo usado exactamente $A$ y $L$ tienen grado impar.

En el mapa completo, los vértices cuya paridad debe cambiar son $A,B,C,E,H,J,K,L.$ Como solo se eliminan $4$ caminos, estos deben emparejar los $8$ vértices. Entre ellos, $E$ es adyacente solo a $A,$ lo que obliga a eliminar $AE$ ; entonces queda forzado $BC$ . Del mismo modo, $H$ es adyacente solo a $L,$ lo que obliga a eliminar $HL,$ y luego $JK.$

El grafo restante es una cadena $\begin{gathered} A-B-F,\\ F-E-I-J-F,\\ F-G,\\ G-C-D-H-G,\\ G-K-L. \end{gathered}$ Cada uno de los dos ciclos de $4$ lados puede recorrerse en cualquiera de los dos sentidos, y todo lo demás queda forzado. Por tanto, hay $2\cdot2=4$ rutas.

Así, E es la respuesta correcta.

Name the four cities in the top row $A,B,C,D,$ those in the middle row $E,F,G,H,$ and those in the bottom row $I,J,K,L.$ A route using $13$ roads is an open Euler trail, so in the used graph exactly $A$ and $L$ have odd degree.

In the full map, the vertices whose degree parity must change are $A,B,C,E,H,J,K,L.$ Because only $4$ roads are removed, those roads must pair these $8$ vertices. Among them, $E$ is adjacent only to $A,$ forcing $AE$ to be removed; then $BC$ is forced. Similarly $H$ is adjacent only to $L,$ forcing $HL,$ and then $JK.$

The remaining graph is a chain $\begin{gathered} A-B-F,\\ F-E-I-J-F,\\ F-G,\\ G-C-D-H-G,\\ G-K-L. \end{gathered}$ Each of the two $4$ -cycles can be traversed in either direction, and everything else is forced. Hence there are $2\cdot2=4$ routes.

Thus, E is the correct answer.

2019 AMC 12B Problema 10

Respuesta: E

Nivel de dificultad: 1640

Pista pequeña:

Pista grande:

Solución:

El Problema 10 en otros años