2019 AMC 12B Problema 10

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.