Question

In the country of Twenty, there are exactly twenty cities, and there is exactly one direct road between any two cities. No two direct roads have an overlapping road segment. After the election dates are announced, candidates from their respective cities start visiting the other cities. Following are the rules that the election commission has laid down for the candidates:
1. Each candidate must visit each of the other cities exactly once.
2. Each candidate must use only the direct roads between two cities for going from one city to another.
3. The candidate must return to his own city at the end of the campaign.
4. No direct road between two cities would be used by more than one candidate.
The maximum possible number of candidates is:

• A. 5
• B. 6
• C. 7
• D. 8
• E. 9

Hint:

In graph theory, whenever there is a complete graph of $n$ vertices, the number of edges is $\binom{n}{2}$. Problems like these usually reduce to dividing the total number of edges by the number required for one complete tour.

Answer 1

Answer: (E)

Step 1: Count the total number of direct roads.
There are 20 cities, and exactly one road between each pair. Hence, the total number of roads = \[ \binom{20}{2} = \frac{20 \times 19}{2} = 190 \]

Step 2: Roads required by one candidate.
Each candidate must start from his city, visit all the other 19 cities exactly once, and return. That means the candidate must cover all 20 edges in a cycle (since 20 cities in total). So, each candidate consumes exactly 20 roads.

Step 3: Maximum candidates possible.
If there are $n$ candidates, the total roads consumed = $20n$. This must be less than or equal to 190. \[ 20n \leq 190 \quad \Rightarrow \quad n \leq 9.5 \] So, maximum integer value is $n=9$.

Step 4: Final Answer.
Thus, the maximum possible number of candidates is: \[ \boxed{9} \]