Figures (i) and (ii) below represent intercity highway systems, where each black dot is a city and each line segment joining two dots is a direct highway between those two cities. Figure (i) is a 4 by 4 grid of cities connected only along the horizontal and vertical grid lines, with no diagonal roads. Figure (ii) has 5 cities joined by 6 highways in an irregular network with one extra interior city.
A salesperson needs to make a trip. She needs to start from a city, visit each of the remaining cities exactly once, and finally return to the same city from which she started. Which one of the following options is then true?
Show Hint
Split the cities into two groups so that every road joins one group to the other, then check whether the two groups are equal in size.
Such a trip is possible for (i), but not for (ii).
Such a trip is possible for (ii), but not for (i).
Such a trip is possible for both (i) and (ii).
Such a trip is possible neither for (i) nor for (ii).
Show Solution
The Correct Option isA
Solution and Explanation
Step 1: Restate the goal.
We want one closed route through each map that touches every dot exactly once and comes back to the start.
Step 2: Build a working route for the grid, figure (i).
Number the rows $1$ to $4$ from top to bottom and the columns $1$ to $4$ from left to right, so a city is $(row,col)$. One route that uses only the grid roads is:
$(1,1) \to (2,1) \to (3,1) \to (4,1) \to (4,2) \to (4,3) \to (4,4) \to (3,4) \to (3,3) \to (3,2) \to (2,2) \to (2,3) \to (2,4) \to (1,4) \to (1,3) \to (1,2) \to (1,1)$.
Every arrow above is a real horizontal or vertical road on the grid, all $16$ cities show up exactly once, and the route ends back where it began. So figure (i) works.
Step 3: Try the same for figure (ii) and see where it breaks.
Call the two well connected cities $A$ and $E$, and the other three $B$, $C$, $D$. Every road runs between an $\{A,E\}$ city and a $\{B,C,D\}$ city, so a route can never move from $B$ straight to $C$, or from $A$ straight to $E$; it always has to hop from one group to the other.
Try building the loop: start at $A$, go to $B$, come back only to $E$ since $B$ only knows $A$ and $E$, go to $C$, come back to $A$ or $E$ again, go to $D$, and come back again. Every single visit to $B$, $C$, or $D$ forces an immediate return to the $\{A,E\}$ pair, but that pair has only $2$ cities to share among $3$ round trips. By the time the third city, $D$, is visited, the route has already used up $A$ and $E$ once each and must reuse one of them to get back, which means passing through it a second time.
Step 4: Conclude.
The grid, figure (i), supports a full loop, but the 5-city network, figure (ii), cannot avoid reusing a city because it does not have enough well connected cities to alternate with all three lightly connected ones.
\[ \boxed{\text{Such a trip is possible for (i), but not for (ii).}} \]
