4
$\begingroup$

Three small towns, designated $A,B,C$ are interconnected by a system of two-way roads as shown in the following picture:

enter image description here

Image of interconnected cities

How many ways are there to go from $A$ to $C$ and come back from $C$ to $A$ such that the connections which are used to go from $A$ to $C$ cannot be used again. For example, if you use ($R_1$ and $R_6$), then they are cancelled for going from $C$ to $A$, you may use the roads ($R_5$ and $R_2$) or use ($R_8)$.

Second example, if you use $R_9$ go from $A$ to $C$, then it will be cancelled, so you can use ($R_8$) or ($R_7$ and $R_1$) or ($R_5$ and $R_3$) etc for going from $C$ to $A$.

My solution: There are $4\cdot3+2=14$ ways to go from $A$ to $C$, I tought that there may be $3\cdot2+1=7$ to come back. However, I am not sure. So, I want help for it..

NOTE: Unnecessary travelling is not allowed, i.e, you should always move to your target, for example if you go from A to B then you cannot shuttle here, you should move from B to C.

$\endgroup$

1 Answer 1

5
$\begingroup$

I will divide this problem into two parts

$1-)$ Move from $A$ to $B$ and $B$ to $C$ :

If we move to $A$ to $C$ by using connector city $B$ , then there are $4 \times 3 = 12$ ways. Now , it is time for coming back , assume that we used the roads $R_1$ and $R_5$ then , we can come back by $3 \times 2 = 6$ ways or using $2$ direct ways , so there are $6+2 =8$ ways to come back.

Result = $12 \times 8 = 96 $ ways

$2-)$ Move from A to C directly : We can select $2$ ways to go directly , so we cannot use one of them to come back from $C$ to $A$ , then there are $4 \times 3 +1 = 13$ ways to come back. Then , $2 \times 13 = 26$ ways to go form $A$ to $C$ and come form $C$ to $A$.

Result = $96 + 26 =122$ ways there are

$\endgroup$
0

You must log in to answer this question.