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......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
- asif e elahi
- Posts:185
- 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
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}})$
NOT,
$$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 .
-
- Posts:5
- Joined:Sat Jan 30, 2021 2:10 pm
Re: BdMO National 2013: Secondary 8, Higher Secondary 6
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]
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]