## BdMO National 2013: Secondary 8, Higher Secondary 6

### BdMO National 2013: Secondary 8, Higher Secondary 6

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.

- Fatin Farhan
**Posts:**75**Joined:**Sun Mar 17, 2013 5:19 pm**Location:**Kushtia,Bangladesh.-
**Contact:**

### Re: BdMO National 2013: Secondary 8, Higher Secondary 6

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.

$$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.

*"The box said 'Requires Windows XP or better'. So I installed*

**L$$i$$nux**...:p"-
**Posts:**461**Joined:**Wed Dec 15, 2010 10:05 am**Location:**Dhaka-
**Contact:**

### Re: BdMO National 2013: Secondary 8, Higher Secondary 6

@Fatin, Not Clear to me at all! Faulty Solution. First, try to explain it clearly.

**You spin my head right round right round,**

When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )

When you go down, when you go down down......

- asif e elahi
**Posts:**183**Joined:**Mon Aug 05, 2013 12:36 pm**Location:**Sylhet,Bangladesh

### Re: BdMO National 2013: Secondary 8, Higher Secondary 6

We induct on n. The result is trivial for $n=1,2$. We assume that it is true for $n=m$. Now we prove that it is true for $n=m+1$. Among $m+1$ cities, if there exists a city which is connected with 0 or 1 city, then there are $m+1$ or m roads among the rest m cities.But by our induction hypothesis, there exists at least one city which satisfies the given condition.So we assume that every city is connected with at least 2 cities.If a city has more than 2 connecting roads then,the number of roads will be greater than $n+1$. So every city has exactly 2 connecting roads.Then the roads and cities form a polygon and all of the cities satisfies the given condition.Thus our induction is complete .

- Fatin Farhan
**Posts:**75**Joined:**Sun Mar 17, 2013 5:19 pm**Location:**Kushtia,Bangladesh.-
**Contact:**

### Re: BdMO National 2013: Secondary 8, Higher Secondary 6

I was trying to tell that it is not possible to come back to its original position without ever traveling the same road twice. Let there be $$C$$ ways to choose $$n$$ roads such that we can not retun to its original position.sourav das wrote:@Fatin, Not Clear to me at all! Faulty Solution. First, try to explain it clearly.

So, 1 road can be chosen in $$n$$ ways.

2 roads can be chosen in $$n(n-1)$$ ways.

3 roads can be chosen in $$n(n-1)(n-2)$$ ways. Bacause we have already a road connecting to its previous city and we don't want to return to its original position.

So, n roads can be chosen in $$n(n-1)(n-2)..............(n-n)$$.

$$ \therefore C= n(n-1)(n-2)..............(n-n)= 0$$.

So, there is 0 ways to choose $$n$$ roads among $$n$$ cities such that we cannot return to its original city.

Thus, it is always possible to return to its original city, no matter how the $$n$$ roads are used.

*"The box said 'Requires Windows XP or better'. So I installed*

**L$$i$$nux**...:p"### Re: BdMO National 2013: Secondary 8, Higher Secondary 6

Here's my approach-

Please

**Install $L^AT_EX$ fonts**in your PC for better looking equations,**Learn****how to write equations**, and**don't forget**to read**Forum Guide and Rules.****"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes**### Re: BdMO National 2013: Secondary 8, Higher Secondary 6

Ahem...

$n(n-1)(n-2)..............({\color{DarkGreen} {n-n+1}})$

$$n(n-1)(n-2)..............({\color{Red} {n-n}})$$

For the sequence that you showed here, no. of ways in which $n$ roads can be chosen is,Fatin Farhan wrote: So, 1 road can be chosen in $$n$$ ways.

2 roads can be chosen in $$n(n-1)$$ ways.

3 roads can be chosen in $$n(n-1)(n-2)$$ ways. Bacause we have already a road connecting to its previous city and we don't want to return to its original position.

So, n roads can be chosen in $$n(n-1)(n-2)..............({\color{Red} {n-n}})$$.

$n(n-1)(n-2)..............({\color{DarkGreen} {n-n+1}})$

**NOT**,$$n(n-1)(n-2)..............({\color{Red} {n-n}})$$

### Re: BdMO National 2013: Secondary 8, Higher Secondary 6

I dont think its necessary for all to have 2 roads. If all have any one has at least 3, then also the condition is satisfiedasif e elahi wrote:We induct on n. The result is trivial for $n=1,2$. We assume that it is true for $n=m$. Now we prove that it is true for $n=m+1$. Among $m+1$ cities, if there exists a city which is connected with 0 or 1 city, then there are $m+1$ or m roads among the rest m cities.But by our induction hypothesis, there exists at least one city which satisfies the given condition.So we assume that every city is connected with at least 2 cities.If a city has more than 2 connecting roads then,the number of roads will be greater than $n+1$. So every city has exactly 2 connecting roads.Then the roads and cities form a polygon and all of the cities satisfies the given condition.Thus our induction is complete .