Select Page

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

But try the problem first…

Source

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.