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"

m (→‎Solution (with some graph theory))
m (→‎Solution 4)
 
(8 intermediate revisions by 6 users not shown)
Line 29: Line 29:
 
<math>\textbf{(A) } 0 \qquad\textbf{(B) } 1 \qquad\textbf{(C) } 2 \qquad\textbf{(D) } 3 \qquad\textbf{(E) } 4</math>
 
<math>\textbf{(A) } 0 \qquad\textbf{(B) } 1 \qquad\textbf{(C) } 2 \qquad\textbf{(D) } 3 \qquad\textbf{(E) } 4</math>
  
−
==Solution (with some graph theory)==
+
==Solution 1 (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.
+
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:
−
First, notice that for any vertex <math>V</math> excluding <math>A</math> and <math>L</math> on the graph, we can visit it at most <math>M(V) = \left\lfloor \frac{\text{deg}(V)}{2} \right\rfloor</math> where deg<math>(V)</math> is the number of edges connected to <math>V</math>. 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.
+
 
 +
''Note:'' <math>\text{X}</math>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 <math>2</math> cities marked with an <math>\text{O}</math> on a path, there are <math>2</math> 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 <math>2\cdot 2 = \boxed{\textbf{(E) } 4}</math> valid paths.
 +
 
 +
==Solution 2 (longer graph theory)==
 +
Let the bottom-left vertex be <math>(0,0)</math>, and let each of the edges have length <math>1</math>, so that all of the vertices are at lattice points.
 +
Firstly, notice that for any vertex <math>V</math> on the graph (other than <math>A</math> or <math>L</math>), we can visit it at most <math>M(V) = \left\lfloor \frac{\text{deg}(V)}{2} \right\rfloor</math> times, where <math>\text{deg}(V)</math> is, as usual, the degree of <math>V</math> (i.e. the number of edges coming into/out of <math>V</math>). 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>
 
<asy>
 
import olympiad;
 
import olympiad;
Line 65: Line 102:
 
label("1", (2,0),S);
 
label("1", (2,0),S);
 
</asy>
 
</asy>
−
Additionally, notice that if we visit <math>n</math> vertices (not necessarily distinct; i.e. if we visit a vertex twice we count it as two vertices) along our path, we must traverse <math>n-1</math> 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 <math>A</math> and <math>L</math> 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 <math>M(V)</math> times and we have to traverse <math>2\cdot M(V)</math> 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 <math>A</math> and <math>L</math>), and any two edges connected to the other vertices along the outside edge of the rectangle.
+
Additionally, notice that if we visit <math>n</math> vertices (not necessarily distinct, i.e. counting a vertex which is visited twice as two vertices) along our path, we must traverse <math>n-1</math> edges (this is quite easy to prove). Thus, if we want to traverse <math>13</math> edges in total, we have to visit <math>14</math> vertices. We must visit <math>A</math> and <math>L</math>, leaving <math>12</math> vertices from the rest of the graph to visit.  
−
With this information, we can proceed with just a few cases.
+
 
 +
If we sum the maximum numbers of visits to each vertex, we find that this is exactly equal to the <math>12</math> found above. This means that we have to visit each vertex <math>M(V)</math> times, and must traverse <math>2\cdot M(V)</math> edges connected to each vertex. Specifically, we must traverse all <math>4</math> of the edges connected to the two central vertices at <math>(1,1)</math> and <math>(1,2)</math>, as well as both edges connected to the <math>2</math> corner vertices (excluding <math>A</math> and <math>L</math>), and any <math>2</math> edges connected to the other vertices along the outside edge of the rectangle.
 +
 
 +
With this information, we can now proceed by dividing into cases.
  
−
<math>\textbf{Case 1: We first move down from A}.</math>
+
'''Case 1''': We first move down from <math>A</math>.
  
−
In this case, we see that we must immediately move right to <math>(1,1)</math> in order to traverse the edge from <math>(0,1)</math> to <math>(1,1)</math> since we can never revisit <math>(0,1)</math>. However, by the same logic, we must immediately move to <math>(0,0)</math>. This is a contradiction, so there are no paths in this case.
+
In this case, we see that we must immediately move right to <math>(1,1)</math> in order to traverse the edge from <math>(0,1)</math> to <math>(1,1)</math>, since we can never revisit <math>(0,1)</math>. However, by the same logic, we must immediately move to <math>(0,0)</math>. This is a contradiction, so there are no possible paths in this case.
  
−
<math>\textbf{Case 2: We first move right from A}.</math>
+
'''Case 2''': We first move right from <math>A</math>.
  
−
Similar to the last case, we see that we must immediately move to <math>(1,1)</math>. By symmetry, we conclude that our last two moves must be <math>(2,1) \rightarrow (2,0) \rightarrow (3,0)</math>. With this information, we have reduced the problem to traveling from <math>(1,1)</math> to <math>(2,1)</math> with the same constraints as before. We redraw the graph, removing the edges we have already used and updating our labels (Note that <math>(1,1)</math> and <math>(2,1)</math> are still labeled with <math>2</math> since we will pass through them twice, including the start and end). Then, we remove the vertices with label 0 and the edges we know we can never traverse, giving us:
+
Similar to the last case, we see that we must immediately move to <math>(1,1)</math>. By symmetry, we conclude that our last two moves must be <math>(2,1) \rightarrow (2,0) \rightarrow (3,0)</math>. With this information, we have reduced the problem to traveling from <math>(1,1)</math> to <math>(2,1)</math> with the same constraints as before. We redraw the graph, removing the edges we have already used and updating our labels (note that <math>(1,1)</math> and <math>(2,1)</math> are still labeled with <math>2</math> since we will pass through them twice, at the start and the end). Then, we remove the vertices with label <math>0</math> and the edges we know we can never traverse, giving:
  
 
<asy>
 
<asy>
Line 105: Line 145:
 
There are two ways to traverse each cycle (clockwise and anti-clockwise), giving us a total of <math>2\cdot 2 = \boxed{\textbf{(E) } 4}</math> paths of length 13 from <math>A</math> to <math>L</math>.
 
There are two ways to traverse each cycle (clockwise and anti-clockwise), giving us a total of <math>2\cdot 2 = \boxed{\textbf{(E) } 4}</math> paths of length 13 from <math>A</math> to <math>L</math>.
  
−
(Solution by vedadehhc)
+
==Solution 3 (Condensed version of Solution 1)==
−
 
+
Observe that only the two central vertices can be visited twice. Since the path is of length 13, we need to repeat a vertex. Using casework on each vertex, we can find there are two paths that go through each central vertex twice, for an answer of <math>\boxed{4}.</math>
−
==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 = <math>\boxed{\textbf{(E) } 4}</math>. 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.
 
−
 
 
−
<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>
 
  
 +
==Solution 4==
 +
Looking at the answer choices we see that it would probably be easy enough to count the different paths. After some experimenting, we find that we must cross one of the middle vertexes twice, making counting easier.
  
−
Now, we find that at each of the 2 cities marked with an O, 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 <math>2*2=\boxed4</math>
+
We finally find that there are <math>\boxed{4}</math> paths that satisfy the conditions. Luckily, <math>4</math> is the largest answer choice so we know it must be correct.
  
 
==See Also==
 
==See Also==
 
{{AMC12 box|year=2019|ab=B|num-b=9|num-a=11}}
 
{{AMC12 box|year=2019|ab=B|num-b=9|num-a=11}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 21:18, 1 February 2020

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

Solution 3 (Condensed version of Solution 1)

Observe that only the two central vertices can be visited twice. Since the path is of length 13, we need to repeat a vertex. Using casework on each vertex, we can find there are two paths that go through each central vertex twice, for an answer of $\boxed{4}.$

Solution 4

Looking at the answer choices we see that it would probably be easy enough to count the different paths. After some experimenting, we find that we must cross one of the middle vertexes twice, making counting easier.

We finally find that there are $\boxed{4}$ paths that satisfy the conditions. Luckily, $4$ is the largest answer choice so we know it must be correct.

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=116515"