2019 AMC 12B Problems/Problem 10

Problem

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.)

!! Someone with good Latex or Asymptote skills please help !!

How many different routes can Paula take?

$\textbf{(A) } 0 \qquad\textbf{(B) } 1 \qquad\textbf{(C) } 2 \qquad\textbf{(D) } 3 \qquad\textbf{(E) } 4$

Solution (with some graph theory)

Let the bottom right vertex be (0,0) and let each of the edges have length 1 so that all of the vertices are at lattice points. First, notice that for any vertex $V$ excluding $A$ and $L$ on the graph, we can visit it at most $M(V) = \left\lfloor \frac{\text{deg}(V)}{2} \right\rfloor$ where deg $(V)$ is the number of edges connected to $V$ . This is because to visit any of these vertices, we would have to visit and exit on two different edges (This is a pretty standard principle in graph theory). We will label each vertex with this number. $[asy] import olympiad; unitsize(40); for (int i = 0; i < 3; ++i) { for (int j = 0; j < 4; ++j) { pair A = (j,i); dot(A); } } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 4; ++j) { if (j != 3) { draw((j,i)--(j+1,i)); } if (i != 2) { draw((j,i)--(j,i+1)); } } } label("$A$", (0,2), W); label("$L$", (3,0), E); label("1", (1,2), N); label("1", (2,2), N); label("1", (3,2), N); label("1", (0,1), W); label("2", (1,1), NW); label("2", (2,1), NW); label("1", (3,1), E); label("1", (0,0),S); label("1", (1,0),S); label("1", (2,0),S); [/asy]$ Additionally, notice that if we visit $n$ vertices (not necessarily distinct; i.e. if we visit a vertex twice we count it as two vertices) along our path, we must traverse $n-1$ edges (this is also pretty easy to prove). Thus, if we want to traverse 13 edges total, we have to visit 14 vertices. We will visit $A$ and $L$ for sure, leaving us with 12 vertices to visit from the rest of the graph. If we add up the maximum number of visits for each vertex, we find that this sum is equal to exactly 12. This means that we have to visit each vertex $M(V)$ times and we have to traverse $2\cdot M(V)$ edges connected to each vertex. Specifically, this tells us that we must traverse all four of the edges connected to the two center vertices ((1,1) and (1,2)), both edges connected to the two corner vertices (excluding $A$ and $L$ ), and any two edges connected to the other vertices along the outside edge of the rectangle. With this information, we can proceed with just a few cases.

\textbf{Case 1: We first move down from A}. In this case, we see that we must immediately move right to $(1,1)$ in order to traverse the edge from $(0,1)$ to $(1,1)$ since we can never revisit $(0,1)$ . However, by the same logic, we must immediately move to $(0,0)$ . This is a contradiction, so there are no paths in this case.

\textbf{Case 2: We first move right from A}. Similar to the last case, we see that we must immediately move to $(1,1)$ . By symmetry, we conclude that our last two moves must be $(2,1) \rightarrow (2,0) \rightarrow (3,0)$ . With this information, we now have to travel from $(1,1)$ to $(2,1)$ with the same constraints as before. We redraw the graph, removing the edges we have already used and updating our labels. Then, we remove the vertices with label 0 and the edges we know we can never traverse, giving us:

$[asy] import olympiad; unitsize(40); for (int i = 0; i < 3; ++i) { for (int j = 0; j < 4; ++j) { if(j==1 && i==2) {continue;} if(j==2 && i==0) {continue;} pair A = (j,i); dot(A); } } draw((0,0)--(1,0)--(1,1)--(0,1)--cycle); draw((2,1)--(3,1)--(3,2)--(2,2)--cycle); draw((1,1)--(2,1)); label("$A$", (0,2), W); label("$L$", (3,0), E); label("1", (2,2), N); label("1", (3,2), N); label("1", (0,1), W); label("1", (1,1), NW); label("1", (2,1), NW); label("1", (3,1), E); label("1", (0,0),S); label("1", (1,0),S); [/asy]$ Now, it is clear that we must complete a cycle in the lower left square, return to $(1,1)$ , go to $(2,1)$ , and complete a cycle in the top right square, returning to $(2,1)$ . There are two ways to traverse each cycle (clockwise and anti-clockwise), giving us a total of $2\cdot 2 = \boxed{\textbf{(E) } 4}$ paths of length 13 from $A$ to $L$ .

(Solution by vedadehhc)

Solution 2

Note the following route, which isn't that hard to discover:

!! Someone with good Latex/Asymptote skills please help !!

Look at the two square "loop"s. Each one can be oriented in one of two directions (lower left: either go down or left first; upper right: either go right or up first). Therefore, the answer is 1 route * 2 * 2 = $\boxed{\textbf{(E) } 4}$ . Note that no choice is larger than it.

Solution 3

Note that of the 12 cities, 6 of them (2 on the top and bottom, 1 on the sides) have 3 edges connecting to them. Therefore, at least 1 edge connecting to them cannot be used. Additionally, the same goes for the start and end point as we don't want to return to them. so we have 8 points that we know have 1 unused edge, and we have a total of 4 unused edges to work with (17-13), so we easily find there is only one configuration that satisfies this:

X's represent unused edges, by necessity, lines are filled in for the paths.

o _ _ _ o ..X.. o _ _ _ o

X ..... | ..... | ..... |

o _ _ _ 0 _ _ _ 0 _ _ _ o

| ..... | ..... | ..... X

o _ _ _ o...X...o _ _ _ o

Now, we find that at each of the 2 cities marked with a 0, we have 2 possibilities to follow the path, we can either continue straight and cross back over it later, or make a left turn and turn right when we approach the junction again/ This gives us $2*2=\boxed4$

2019 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 9	Followed by Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search

2019 AMC 12B Problems/Problem 10

Contents

Problem

Solution (with some graph theory)

Solution 2

Solution 3

See Also