Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 AMC 12B Problems/Problem 10"

(Thoroughly cleaned up the solutions for LaTeX, formatting, and grammar; added more detail to the solutions to improve clarity; and re-ordered the two solutions to put the easier one first)
m (Further improved clarity)
Line 30: Line 30:
  
 
==Solution 1 (graph theory)==
 
==Solution 1 (graph theory)==
−
Note that of the <math>12</math> cities, <math>6</math> of them (<math>2</math> on the top, <math>2</math> on the bottom, and <math>1</math> on each side) have <math>3</math> edges coming into/out of them (i.e., in graph theory terms, they have degree <math>3</math>). Therefore, at least <math>1</math> edge connecting to each of these cities cannot be used. Additionally, the same applies to the start and end points, since we don't want to return to them. Thus there are <math>6+2=8</math> vertices that we know have <math>1</math> unused edge, and we have a total of <math>17-13=4</math> unused edges to work with. It is not hard to find that there is only one configuration satisfying these conditions:
+
Note that of the <math>12</math> cities, <math>6</math> of them (<math>2</math> on the top, <math>2</math> on the bottom, and <math>1</math> on each side) have <math>3</math> edges coming into/out of them (i.e., in graph theory terms, they have degree <math>3</math>). Therefore, at least <math>1</math> edge connecting to each of these cities cannot be used. Additionally, the same applies to the start and end points, since we don't want to return to them. Thus there are <math>6+2=8</math> vertices that we know have <math>1</math> unused edge, and we have <math>17-13=4</math> unused edges to work with (since there are <math>17</math> edges in total, and we must use exactly <math>13</math> of them). It is not hard to find that there is only one configuration satisfying these conditions:
  
 
''Note:'' <math>\text{X}</math>s represent unused edges.
 
''Note:'' <math>\text{X}</math>s represent unused edges.

Revision as of 19:20, 18 February 2019

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.) [asy] import olympiad; unitsize(50); 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); [/asy]

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 1 (graph theory)

Note that of the $12$ cities, $6$ of them ($2$ on the top, $2$ on the bottom, and $1$ on each side) have $3$ edges coming into/out of them (i.e., in graph theory terms, they have degree $3$). Therefore, at least $1$ edge connecting to each of these cities cannot be used. Additionally, the same applies to the start and end points, since we don't want to return to them. Thus there are $6+2=8$ vertices that we know have $1$ unused edge, and we have $17-13=4$ unused edges to work with (since there are $17$ edges in total, and we must use exactly $13$ of them). It is not hard to find that there is only one configuration satisfying these conditions:

Note: $\text{X}$s represent unused edges.

[asy] import olympiad; unitsize(50); 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("X", (0, 1.5)); label("X", (1.5, 2)); label("X", (1.5, 0)); label("X", (3, 0.5)); label("O", (1,1), NE); label("O", (2,1), NE); [/asy]

Observe that at each of the $2$ cities marked with an $\text{O}$ on a path, there are $2$ possibilities: we can either continue straight and cross back over the path later, or we can make a left turn, then turn right when we approach the junction again. This gives us a total of $2\cdot 2 = \boxed{\textbf{(E) } 4}$ valid paths.

Solution 2 (longer graph theory)

Let the bottom-left vertex be $(0,0)$, and let each of the edges have length $1$, so that all of the vertices are at lattice points. Firstly, notice that for any vertex $V$ on the graph (other than $A$ or $L$), we can visit it at most $M(V) = \left\lfloor \frac{\text{deg}(V)}{2} \right\rfloor$ times, where $\text{deg}(V)$ is, as usual, the degree of $V$ (i.e. the number of edges coming into/out of $V$). This is because to visit any of these vertices, we would have to enter and exit it by two different edges, in order to avoid using any portion of a road more than once. (Those who know some graph theory will recognise this a well-known principle.) We will label each vertex with this number. [asy] import olympiad; unitsize(50); 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. counting a vertex which is visited twice we as two vertices) along our path, we must traverse $n-1$ edges (this is quite easy to prove). Thus, if we want to traverse $13$ edges in total, we have to visit $14$ vertices. We must visit $A$ and $L$, leaving $12$ vertices from the rest of the graph to visit.

If we sum the maximum numbers of visits to each vertex, we find that this is exactly equal to the $12$ found above. This means that we have to visit each vertex $M(V)$ times, and must traverse $2\cdot M(V)$ edges connected to each vertex. Specifically, we must traverse all $4$ of the edges connected to the two central vertices at $(1,1)$ and $(1,2)$, as well as both edges connected to the $2$ corner vertices (excluding $A$ and $L$), and any $2$ edges connected to the other vertices along the outside edge of the rectangle.

With this information, we can now proceed by dividing into cases.

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 possible paths in this case.

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 have reduced the problem to traveling 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 (note that $(1,1)$ and $(2,1)$ are still labeled with $2$ since we will pass through them twice, at the start and the end). Then, we remove the vertices with label $0$ and the edges we know we can never traverse, giving:

[asy] import olympiad; unitsize(50); 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("2", (1,1), NW); label("2", (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$.

See Also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AMC_12B_Problems/Problem_10&oldid=103418"