There are 6 cities, of which each is connected to every other city. How many…
2025
There are 6 cities, of which each is connected to every other city. How many different routes can one trace from A to B, such that no city is touched more than once in any one route.
- A.
48
- B.
56
- C.
78
- D.
65
Attempted by 5 students.
Show answer & explanation
Correct answer: D
Answer: 65
Explanation:
There are 6 cities in total. Fix A and B as endpoints. The remaining 4 cities can be used as intermediate stops. For a route that uses r intermediate cities (r = 0,1,2,3,4), the number of distinct routes equals the number of permutations of 4 cities taken r at a time, because the order of intermediate cities matters and no city is repeated.
r = 0 (direct): 1 way
r = 1: P(4,1) = 4 ways
r = 2: P(4,2) = 4 × 3 = 12 ways
r = 3: P(4,3) = 4 × 3 × 2 = 24 ways
r = 4: P(4,4) = 4 × 3 × 2 × 1 = 24 ways
Total number of simple routes from A to B = 1 + 4 + 12 + 24 + 24 = 65.
This matches the selected answer 65.