2019 AMC 12B Problems/Problem 10

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

!! Someone with good Latex or Asymptote skills please help !!

How many different routes can Paula take?

Solution

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 = . Note that no choice is larger than it.

Solution 2

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.

o _ _ _ o X o _ _ _ o

X | | |

o _ _ _ 0 _ _ _ 0 _ _ _ o

| | | X

o _ _ _ o X o _ _ _ o

Now, we find that at each of the 2 cities marked with a 0, 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

See Also

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