[Math] Number of routes between two towns

combinatoricsproof-verification

There are seven different roads between town A and town B, four different roads between town B and town C, and two different roads between town A and town C.

(a) How many different routes are there from A to C altogether?

(b) How many different routes are there from A to C and back (any road can be used once in each direction)?

(c) How many different routes are there from A to C and back in part (b) that visit B at least once?

(d) How many different routes are there from A to C and back in part (b) that do
not use any road twice?

I want to verify if my method is correct.
(a) $2$ (direct routes A to C)$+7\times4$ (indirect routes A to C)
(b) $30$ (routes for going from A to C)$\times30$ (routes for going from C to A, since any road can be used once in each direction).
(c) $900$ (total routes) $- 4$ (Number of routes that do not visit B).
(d) $2$ (direct route from A to C) $\times 29$ (route back to A from unused path)+$28$ (indirect route from A to C) $\times (6\times3+2)$ (remaining unused routes).

Best Answer

(a) $2$ (direct routes A to C)$+7\times4$ (indirect routes A to C)

Looks correct to me. Note they didn't state it exactly, but I guess a "route" isn't allowed to visit A or C in the middle (it has to start at A, end at C, and not visit the same city twice).

(b) $30$ (routes for going from A to C)$\times30$ (routes for going from C to A, since any road can be used once in each direction).

Looks correct.

(c) $900$ (total routes) $- 4$ (Number of routes that do not visit B).

Right -- assuming that we only have to visit $B$ in at least one direction (not in both directions), there are only $4$ ways to not do so.

(d) $2$ (direct route from A to C) $\times 29$ (route back to A from unused path)+$28$ (indirect route from A to C) $\times (6\times3+2)$ (remaining unused routes).

Right. Nice work, I can't find any flaws.

Related Question