Question 84

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:

Each candidate must visit each of the other cities exactly once.

Each candidate must use only the direct roads between two cities for going from one city to another.

The candidate must return to his own city at the end of the campaign.

No direct road between two cities would be used by more than one candidate.

The maximum possible number of candidates is


There are 20 cities and one direct road between any 2 cities.

=> Total number of paths = $$C^{20}_2$$

= $$\frac{20 \times 19}{1 \times 2} = 190$$

Now, each candidate needed to visit all the cities and then come back to the city he started from

=> Paths taken by each candidate = $$20$$

Let maximum number of candidates = $$n$$

=> $$20 n < 190$$

=> $$n < \frac{190}{20}$$

=> $$n < 9.5$$

$$\therefore$$ Maximum possible number of candidates = $$9$$

Create a FREE account and get:

  • All Quant Formulas and shortcuts PDF
  • 15 XAT previous papers with solutions PDF
  • XAT Trial Classes for FREE


    Boost your Prep!

    Download App