Towns and Roads

**smart_coder** · 03-12-2007

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) ?

**psuresh1982** · 03-13-2007

I think the answer is 82.

---------------
suresh

**Manojks** · 03-13-2007

I think the answer is 62...

**smart_coder** · 03-13-2007

Explain ur solutions plz!

**Manojks** · 03-13-2007

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

**smart_coder** · 03-13-2007

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 ?

**Manojks** · 03-13-2007

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

**smart_coder** · 03-13-2007

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

**jamesravid** · 03-14-2007

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?

**Manojks** · 03-14-2007

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

**smart_coder** · 03-14-2007

Manoj i askd minimum roads for A -> C -> B.
Not for other routes

**jamesravid** · 03-15-2007

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.

Thread: Towns and Roads

Thread Tools

Display

Hybrid View

Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Re: Towns and Roads

Posting Permissions

About us

GeekInterview

Interact