Try this beautiful problem from the Pre-RMO, 2017 based on Number of ways.

Number of ways – PRMO 2017


There are five cities A, B, C, D, E on a certain island. Each city is connected to every other city by road, find numbers of ways can a person starting from city A come back to A after visiting some cities without visiting a city more than once and without taking the same road more than once. (The order in which he visits the cities such as A \(\rightarrow\) B \(\rightarrow\) C \(\rightarrow\) A and A \(\rightarrow\) C \(\rightarrow\) B \(\rightarrow\) A are different).

  • is 107
  • is 60
  • is 840
  • cannot be determined from the given information

Key Concepts


Number of ways

Integers

Combinatorics

Check the Answer


But try the problem first…

Answer: is 60.

Source
Suggested Reading

PRMO, 2017, Question 9

Combinatorics by Brualdi

Try with Hints


First hint

A B C D E in this way orderwise such that from A person can visit B,C return to A in {4 \choose 2} with 2! ways of approach

from A person visits B, C, D comes back to A in {4 \choose 3} with 3! ways of approach

from A person visits B, C, D, E comes back to A in {4 \choose 4} with 4! ways of approach

Second Hint

ways=\({4 \choose 2}(2!)+{4 \choose 3}(3!)+{4 \choose 4}(4!)\)

Final Step

=12+24+24

=12+48

=60.

Subscribe to Cheenta at Youtube