Travelling from city A to B, then B to A.

Question

I found a permutation problem like "show that there is a ... number of ways of..." which is given below. I tried to show that, but I got a different answer. I will describe how I did, after stating the problem.

Here is the problem:

There are $5$ roads connecting the cities $A$ and $B$. $3$ men want to travel from $A$ to $B$, then again $B$ to $A$. If the journeys $AB$ and $BA$ must be not on the same road and no two men can use the same road when traveling from one city to another city, show that there are $1440$ ways they can travel.

First, I found there are $5\times4\times3=60$ ways they can travel from $A$ to $B$. Similarly, without any special case, there are $60$ ways of traveling from $B$ to $A$. Considering one permutation of traveling from $A$ to $B$, there are $12+9+7=28$ different ways to travel from $B$ to $A$, when at least one man is using the same way. Because the number of different ways to return when

1. the first man reuses a road is $4\times3=12$,
2. the second man reuses but the first man does not is $12-3=9$,
3. the third man reuses but the first and second do not is $12-3-2=7$.

Therefore, the total number of ways they can travel is $60\times(60-28)=1920$, which is not the result given.

What was the mistake? Please, explain the correct method. Sorry for the faults in explaining.

Thank you.

Answer 1

As Daniel Mathias stated in the comments, your solution is correct.

Here is another method of solving the problem:

As you observed, there are $5 \cdot 4 \cdot 3$ ways for the three people to take three different routes from $A$ to $B$.

Since there are six one-way trips and oly five available roads, at least one person must travel from $B$ to $A$ by a route another person took to get from $A$ to $B$.

Exactly one person travels from $B$ to $A$ by a route another person took to get from $A$ to $B$: There are three ways to select the person who travels from $B$ to $A$ by a route another person took to travel from $A$ from $B$, two ways for that person to select one of those two routes, and $2!$ ways for the remaining two people to travel from $B$ to $A$ by the two routes nobody took from $A$ to $B$. Hence, there are $$3 \cdot 2 \cdot 2!$$ ways for the three people to return from $B$ to $A$ for each of the $5 \cdot 4 \cdot 3$ ways they could have traveled from $A$ to $B$.

Exactly two people travel from $B$ to $A$ by a route another person took to get from $A$ to $B$: There are $\binom{3}{2}$ ways to select the two people who travel from $B$ to $A$ by a route another person took from $A$ to $B$. They can either both select to return by the route the other took to get from $A$ to $B$ or exactly one of them can do so, with the other selecting the route the third person took to get there, giving $1 + 2 = 3$ choices. The third person must return using one of the two routes nobody used to travel from $A$ to $B$. Hence, there are $$\binom{3}{2} \cdot (1 + 2) \cdot 2$$ ways for the three people to travel from $B$ to $A$ for each of the $5 \cdot 4 \cdot 3$ ways they could have traveled from $A$ to $B$.

All three people travel from $B$ to $A$ by a route another person took from $A$ to $B$: There are $2$ ways this can occur for each of the $5 \cdot 4 \cdot 3$ ways they could have traveled from $A$ to $B$, namely the oldest person returns by the route the next oldest person took from $A$ to $B$, the second oldest person returns by the route the youngest person took from $A$ to $B$, and the youngest person returns by the route the oldest person took from $A$ to $B$, or the oldest person returns by the route the youngest person took from $A$ to $B$, the next oldest person returns by the route the oldest person took from $A$ to $B$, and the youngest person returns by the route the second oldest person took from $A$ to $B$.

Total: Since these cases are mutually exclusive and exhaustive, the number of ways three people can travel from $A$ to $B$ and return from $B$ to $A$ on the five roads connecting the cities if they each take different routes from $B$ to $A$ than they took from $A$ to $B$ and no two of them take the same route in the same direction is $$5 \cdot 4 \cdot 3\left[3 \cdot 2 \cdot 2! + \binom{3}{2} \cdot (1 + 2) \cdot 2 + 2\right] = 1920$$