Question

Eight cities A, B, C, D, E, F, G and H are connected with one-way roads \(R_1\), \(R_2\), \(R_3\), \(R_4\), \(R_5\) and \(R_6\) in the following manner:
- \(R_1\) leads from A to C via B;
- \(R_2\) leads from C to D and then via B to F;
- \(R_3\) leads from D to A and then via E to H;
- \(R_4\) leads from F to B via G;
- \(R_5\) leads from G to D; and
- \(R_6\) leads from F to H.

The minimum number of road segments that have to be blocked in order to make all traffic from B to D impossible is:

• A. 5
• B. 4
• C. 3
• D. 2

Hint:

Find how many road segments point directly into D, and how many separate routes from B reach those segments.

Answer 1

The Correct Option is D

Step 1: Break every road into its individual one-way segments.
Each road description names the cities it passes through in order, so split each one into the actual directed segments it uses:
\(R_1\): A \(\to\) B, B \(\to\) C
\(R_2\): C \(\to\) D, D \(\to\) B, B \(\to\) F
\(R_3\): D \(\to\) A, A \(\to\) E, E \(\to\) H
\(R_4\): F \(\to\) G, G \(\to\) B
\(R_5\): G \(\to\) D
\(R_6\): F \(\to\) H

Step 2: Find every route from B to D.
Look at only the segments that start at B: B \(\to\) C and B \(\to\) F.
From C, the only onward segment is C \(\to\) D, so one route is B \(\to\) C \(\to\) D.
From F, the segments are F \(\to\) G and F \(\to\) H. F \(\to\) H is a dead end, since H has no segment leading out. From G, the segments are G \(\to\) B (back to the start) and G \(\to\) D, so a second route is B \(\to\) F \(\to\) G \(\to\) D.
These two routes, B-C-D and B-F-G-D, share no common segment.

Step 3: Notice that D has only two ways in.
Checking every listed segment, the only two segments that end at D anywhere in the network are C \(\to\) D and G \(\to\) D. There is no other segment pointing into D.
So every route that ends at D, however long or roundabout, has to finish with one of these two segments.

Step 4: Decide how many segments must be blocked.
Blocking C \(\to\) D alone still leaves B \(\to\) F \(\to\) G \(\to\) D open.
Blocking G \(\to\) D alone still leaves B \(\to\) C \(\to\) D open.
Blocking B \(\to\) C alone still leaves B \(\to\) F \(\to\) G \(\to\) D open, and blocking B \(\to\) F alone still leaves B \(\to\) C \(\to\) D open.
So no single segment can stop both routes. But blocking both C \(\to\) D and G \(\to\) D together removes every way into D, so all traffic to D stops, including from B.

Final Answer:
The minimum number of segments that must be blocked is 2.
\[ \boxed{2} \]