2019 AMC 12B Problems/Problem 10
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
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.
|2019 AMC 12B (Problems • Answer Key • Resources)|
|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|