Track / Stage 4 / 156 of 340 #416 of 1964

Problem 416

AMC 12 late, AIME early

Combinatorics Difficulty 4.9 Find the answer

1. (10 points) In country $B$ , there are 4 southern cities and 5 northern cities. Transportation links connect each southern city with each northern city in both directions; there is no transportation link between other pairs of cities. A traveler starts from a certain southern city, plans to visit all southern cities once and return to the starting point. How many different route options for such a journey exist?

a) $4!\times 5$ !;

b) $3!\times 5^{4}$ ;

c) $4^{4} \times 4$ !;

d) $3^{4} \times 5$ !;

e) another answer.

Your answer

Multiple choice: answer with the letter of the option you want.

Official solution

Answer: b).

Solution. Since there is no direct transportation between the southern cities, when moving from one southern city to another southern city, a transfer will have to be made in some northern city. The number of ways to visit the remaining southern cities is $(4-1)!$ ; the number of ways to choose a northern city for one transfer is 5. To return to the original southern city, 4 transfers in northern cities are required. From this, we get the answer.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.