Math Olympiad-2

[Mosammat Arifa Akter]

2. There are n cities in the country. Between any two cities there is at most one road. Suppose that the total number of roads is n. Prove that there is a city such that starting from there it is possible to come back to it without ever traveling the same road twice.

Answer: Let therebe C ways to take n points such that it is not possible to return to its original position. So, we can take 1 point in (n−1). 2 points be taken in (n−1)(n−2) ........... So n points can be taken (n−1)(n−2)(n−3)(n−n+1)(n−n)
C=(n−1)(n−2)(n−n+1)(n−n)=0.
So, there is 0 ways to take n points such that it is not possible to return to its original position. So,it is always possible to return to its original position.