Painful Paths
Source: 2019 AMC 12B #10
February 14, 2019
AMCAMC 12 BAMC 12
Problem Statement
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?[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("", (0,2), W);
label("", (3,0), E);
[/asy]