-
Expert Member
Towns and Roads
There are 3 towns A, B & C. Each pair is connected with a network of roads.
There are 82 different roads from A to B ( including those that goes through C) .There are 62 different roads from B to C ( including those that goes through A) . What is the smallest number of roads from Ato C ( including those that goes through B) ?
-
Contributing Member
Re: Towns and Roads
I think the answer is 82.
---------------
suresh
-
Expert Member
Re: Towns and Roads
I think the answer is 62...
-
Expert Member
Re: Towns and Roads
Explain ur solutions plz!
-
Expert Member
Re: Towns and Roads
A to B ( including those that goes through C) = 82
Here all 82 roads goes directly from A to B none of the roads from A to C to B.
B to C ( including those that goes through A) = 62
Here all 62 roads goes directly from B to C none of the roads from B to A to C
By having this there is no road from A to C directly. Then the alternative path is A to B to C. So 82 roads from A to B and after B there are only 62 roads from B to C. So My answer is 62.
Thanks
Manoj
-
Expert Member
Re: Towns and Roads
Ur comment:
A to B ( including those that goes through C) = 82
Here all 82 roads goes directly from A to B none of the roads from A to C to B.
why there is no road like A -> C -> B ?
-
Expert Member
Re: Towns and Roads
This is what i assumed only direct roads from A -> B and B -> C
Because its not compulsory to have road from A -> C -> B
Thanks
Manoj
-
Expert Member
Re: Towns and Roads
But it is said that those 82 roads include dose roads also which passes through C. So dere may be a possiblilty that there are such type of roads like a-> c->b
-
Expert Member
Re: Towns and Roads
It is really a toughest puzzle i have seen....
Assume that,
There are 'a' routes from A to B those that does not go through C
There are 'b' routes from B to C those that does not go through A
There are 'c' routes from A to C those that does not go through B
then,
a + bc =82 ( a number of routes directly from A to B + b diff ways to reach Bto C and c diff ways to reach C to A)
b + ac = 62 and we need c+ab
I can't proceed from here....
Even i donno i am going in a right direction or not....
Smart Coder could you give me a hint?
-
Expert Member
Re: Towns and Roads
Smart coder u told minimum roads thats y i assumed like that... I think my answer is not breaking any rules in the question...
Thanks
Manoj
-
Expert Member
Re: Towns and Roads
Manoj i askd minimum roads for A -> C -> B.
Not for other routes
-
Expert Member
Re: Towns and Roads
I got the answer... it is 46.
let me proceed from my previous post,
a + bc =82 --- (1)
b + ac = 62 ---(2)
(1) -(2) => a -b + c(b -a) = 20
(b-a)(c-1) =20
since a,b and c are intergers,
(b-a,c-1) must be any one of the following (1,20), (2,10), (4.5), (5,4), (10,2) and (20,1).
if (b-a,c-1) = (20,1)
then c=2 b=a+20 apply this in (1) we get
a +2a+40 =82 =>a =14 and b=34
which is not possible since c+ab can not be more than 82.
if we proceed like this remove all the pair of values except (2,10)
if (b-a,c-1) = (2,10)
c=11 and b = a+2 apply this in (1) we get
a + 11a+22 =82 => a =5 and b=7
verify these values by applying them in (2) 7 + 5 * 11 =62.
All we need is c+ab = 11 + 5 * 7 =46
Hence number of routes between A and C is exactly 46.
Smart Coder it is a wonderful puzzle i never faced before...thanx for posting this and keep up the great work.
Last edited by jamesravid; 03-15-2007 at 12:19 AM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
Reply With Quote