Passage

Directions for the following 3 (three) items : Consider the given information and answer the three items that follow. Eight railway stations A, B, C, D, E, F, G and H are connected either by two-way passages or one-way passages. One-way passages are from C to A, E to G, B to F, D to H, G to C, E to C and H to G. Two-way passages are between A and E, G and B, F and D, and E and D.

In how many different ways can a train travel from F to A without passing through any station more than once?

(a) 1
(b) 2
(c) 3
(d) 4 ✓ UPSC's answer

Why the answer is (d)

• From F the only way out is the two-way F–D (B to F is one-way into F). From D the train can go to H or E.

• Via H: H goes only to G; from G, C then A works (G to B leads back to F, already visited). Route: F–D–H–G–C–A.

• Via E: E–A directly; E–C–A; and E–G–C–A. Routes: F–D–E–A, F–D–E–C–A, F–D–E–G–C–A.

• That is 4 routes in all, option (d).

Why the other options are wrong

(a) 1: There are more than one valid path, specifically four distinct routes exist.
(b) 2: There are more than two valid paths; the count is four.
(c) 3: There are more than three valid paths; the fourth path F-D-E-G-C-A is also valid.

Asked in the CSAT Paper II of the UPSC Civil Services Preliminary Examination 2017, held on 18 June 2017. Question and answer key: Union Public Service Commission. Explanation: UPSC Answer Check.