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

BdMO
Posts: 134
Joined: Tue Jan 18, 2011 1:31 pm

### 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
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.
"The box said 'Requires Windows XP or better'. So I installed L\$\$i\$\$nux...:p"

sourav das
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\$" )

asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm

### 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
Contact:

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

sourav das wrote:@Fatin, Not Clear to me at all! Faulty Solution. First, try to explain it clearly.
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.
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"

Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm
Contact:

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

Here's my approach-
We will prove this by contradiction. Let's assume that it is possible to make \$n\$ roads in such a way that no matter which city we start from, we cannot come back to it by traversing each road only once.
Let's call a group of connected cities a "Zone". In other words, if there is a way to go from city A to city B in some way, they are in the same "Zone".
If two cities are in the same zone, there is already a way to get from one city to the other. Thus, making a road between two cities in the same zone would make sure that we can go back to the starting city without traversing a road twice and contradict our very claim. So we'll always make roads between cities from different zones .
Let's assume, there is no road initially. Therefore, there are \$n\$ zones (since there are as many isolated cities).
Now, if we make a road, 2 zones get concatenated. In other words, the number of the zones gets reduced by \$1\$ every time we connect two cities from different zone by a new road. Thus, when we are done making \$n-1\$ roads, we'll have only \$(n-n+1) = 1\$ zone left. So, if we have to make the \$n^{th}\$ road, we'll have to connect two cities from the same zone and thus make sure that we can find such a city, starting from which, we can come back to it without traversing a road twice. [Proved]
Learn how to write equations, and don't forget to read

"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes

sowmitra
Posts: 155
Joined: Tue Mar 20, 2012 12:55 am

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

Ahem...
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}})\$\$.
For the sequence that you showed here, no. of ways in which \$n\$ roads can be chosen is,
\$n(n-1)(n-2)..............({\color{DarkGreen} {n-n+1}})\$
NOT,
\$\$n(n-1)(n-2)..............({\color{Red} {n-n}})\$\$
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

Siam
Posts: 13
Joined: Sun Mar 17, 2013 3:36 pm

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

asif 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 .
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 satisfied