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 (with some 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. First, notice that for any vertex excluding and on the graph, we can visit it at most where deg is the number of edges connected to . 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. Additionally, notice that if we visit vertices (not necessarily distinct; i.e. if we visit a vertex twice we count it as two vertices) along our path, we must traverse 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 and 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 times and we have to traverse 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 and ), 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.
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 paths in this case.
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, including the start and end). Then, we remove the vertices with label 0 and the edges we know we can never traverse, giving us:
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 by vedadehhc)
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.
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
|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|