Question

What is the number of routes from \(P\) to \(Q\) in the network shown?

• A. 5
• B. 6
• C. 9
• D. 12

Hint:

Trace every left-to-right arrow path from \(P\) to \(Q\) one node at a time, and count separately the routes through node 1, through node 2 directly, and through node 3, being careful not to double count paths that reach node 2 via node 1 or node 3.

Answer 1

The Correct Option is C

A different way to count the same routes is to sort them by which node they use right before reaching $Q$, either node 4 or node 5, instead of sorting them by the first node they visit after $P$.

1. Routes ending in $4 \to Q$: $P \to 1 \to 4 \to Q$, $P \to 2 \to 4 \to Q$, $P \to 3 \to 4 \to Q$, $P \to 1 \to 2 \to 4 \to Q$, and $P \to 3 \to 2 \to 4 \to Q$. That is 5 distinct paths.
2. Routes ending in $5 \to Q$: $P \to 1 \to 5 \to Q$, $P \to 2 \to 5 \to Q$, $P \to 1 \to 2 \to 5 \to Q$, and $P \to 3 \to 2 \to 5 \to Q$. That is 4 distinct paths.

Let's summarize:

• Every route must enter $Q$ from either node 4 or node 5, since those are the only two arrows pointing into $Q$.
• Splitting the count this way avoids double counting, because no single route can pass through both node 4 and node 5.

Adding the two groups gives $5 + 4 = 9$ routes in total, the same answer found by grouping from the P side.