Difference between revisions of "2019 AMC 12B Problems/Problem 10"
(→Solution (with some graph theory)) |
m (→Solution 4) |
||
(11 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 | + | ==Solution 1 (graph theory)== |
− | Let the bottom | + | 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. | ||
+ | |||
+ | <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 | + | 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. |
− | |||
− | <math> | + | 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. |
− | |||
− | <math> | + | With this information, we can now proceed by dividing into cases. |
− | 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 | + | |
+ | '''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 possible paths in this case. | ||
+ | |||
+ | '''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, 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 94: | Line 136: | ||
label("1", (3,2), N); | label("1", (3,2), N); | ||
label("1", (0,1), W); | label("1", (0,1), W); | ||
− | label(" | + | label("2", (1,1), NW); |
− | label(" | + | label("2", (2,1), NW); |
label("1", (3,1), E); | label("1", (3,1), E); | ||
label("1", (0,0),S); | label("1", (0,0),S); | ||
Line 103: | 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 | + | ==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 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 <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 22:18, 1 February 2020
Contents
Problem
The figure below is a map showing cities and
roads connecting certain pairs of cities. Paula wishes to travel along exactly
of those roads, starting at city
and ending at city
, 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?
Solution 1 (graph theory)
Note that of the cities,
of them (
on the top,
on the bottom, and
on each side) have
edges coming into/out of them (i.e., in graph theory terms, they have degree
). Therefore, at least
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
vertices that we know have
unused edge, and we have
unused edges to work with (since there are
edges in total, and we must use exactly
of them). It is not hard to find that there is only one configuration satisfying these conditions:
Note: s represent unused edges.
Observe that at each of the cities marked with an
on a path, there are
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
valid paths.
Solution 2 (longer graph theory)
Let the bottom-left vertex be , and let each of the edges have length
, so that all of the vertices are at lattice points.
Firstly, notice that for any vertex
on the graph (other than
or
), we can visit it at most
times, where
is, as usual, the degree of
(i.e. the number of edges coming into/out of
). 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.
Additionally, notice that if we visit
vertices (not necessarily distinct, i.e. counting a vertex which is visited twice as two vertices) along our path, we must traverse
edges (this is quite easy to prove). Thus, if we want to traverse
edges in total, we have to visit
vertices. We must visit
and
, leaving
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 found above. This means that we have to visit each vertex
times, and must traverse
edges connected to each vertex. Specifically, we must traverse all
of the edges connected to the two central vertices at
and
, as well as both edges connected to the
corner vertices (excluding
and
), and any
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 .
In this case, we see that we must immediately move right to in order to traverse the edge from
to
, since we can never revisit
. However, by the same logic, we must immediately move to
. This is a contradiction, so there are no possible paths in this case.
Case 2: We first move right from .
Similar to the last case, we see that we must immediately move to . By symmetry, we conclude that our last two moves must be
. With this information, we have reduced the problem to traveling from
to
with the same constraints as before. We redraw the graph, removing the edges we have already used and updating our labels (note that
and
are still labeled with
since we will pass through them twice, at the start and the end). Then, we remove the vertices with label
and the edges we know we can never traverse, giving:
Now, it is clear that we must complete a cycle in the lower left square, return to
, go to
, and complete a cycle in the top right square, returning to
.
There are two ways to traverse each cycle (clockwise and anti-clockwise), giving us a total of
paths of length 13 from
to
.
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
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 paths that satisfy the conditions. Luckily,
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.