Page 1 of 1

BdMO National 2013: Secondary 8, Higher Secondary 6

Posted: Fri Jan 10, 2014 1:39 am
by BdMO
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.

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

Posted: Sun Jan 12, 2014 9:07 pm
by Fatin Farhan
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.

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

Posted: Mon Jan 13, 2014 1:31 pm
by sourav das
@Fatin, Not Clear to me at all! Faulty Solution. First, try to explain it clearly.

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

Posted: Mon Jan 13, 2014 4:33 pm
by asif e elahi
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 . :D

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

Posted: Mon Jan 13, 2014 5:20 pm
by Fatin Farhan
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.

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

Posted: Tue Jan 14, 2014 2:20 am
by Labib
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]

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

Posted: Tue Jan 14, 2014 1:57 pm
by sowmitra
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}})$$

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

Posted: Tue Jan 14, 2014 5:55 pm
by Siam
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 . :D
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

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

Posted: Sun Dec 25, 2022 1:12 pm
by A.K.M.Zakaria
Suppose there are 2 cities and between them there will be only 1 road.. but the number of cities and roads is n.. so there can't be 2 cities.. if we consider there are 3 cities then we'll have exact 3 roads..but if the number of the cities more than 3; suppose it's 4.. then we'll have 6 roads..it creates a quadrilateral and the number of the roads will be 4 sides+2 diagonals=6...

So the number of cities and roads is n=3.. now we have a triangle... And if we start from any of this cities we can come back to it in 2 ways and without traveling 1 road twice...[proved]