UPSC Prelims 2017 CSAT Paper II · Q77 of 79 Comprehension medium

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?

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

Why the answer is (d)

• First, identify all possible paths from F to A by tracing the connections: F connects to B (via B->F one-way, so F->B is not allowed, wait, B to F is one-way, so F cannot go to B directly. Let's re-read: 'One-way passages are from ... B to F'. So F cannot go to B. F connects to D via two-way passage F-D. So F -> D is possible.)

• From D, the train can go to H (via D->H one-way) or to E (via two-way D-E). It cannot go to F (visited) or B (no direct link from D to B, only G-B and B-F). Wait, D connects to H and E. Also, is there a link from D to anywhere else? No. So from D, options are H or E.

• Path 1: F -> D -> H. From H, the only outgoing link is H -> G. So F -> D -> H -> G. From G, links are G -> C and G -> B (two-way). So G can go to C or B.

• If G -> C: From C, link is C -> A. So F -> D -> H -> G -> C -> A. This is a valid path (1).

• If G -> B: From B, link is B -> F. But F is visited. So this path is invalid.

• Path 2: F -> D -> E. From E, links are E -> G, E -> C, and E -> A (two-way A-E). So E can go to G, C, or A.

• If E -> A: F -> D -> E -> A. This is a valid path (2).

• If E -> C: From C, link is C -> A. So F -> D -> E -> C -> A. This is a valid path (3).

• If E -> G: From G, links are G -> C and G -> B.

• If G -> C: From C, link is C -> A. So F -> D -> E -> G -> C -> A. This is a valid path (4).

• If G -> B: From B, link is B -> F. F is visited. Invalid.

• Total valid paths are: 1) F-D-H-G-C-A, 2) F-D-E-A, 3) F-D-E-C-A, 4) F-D-E-G-C-A.

• Therefore, there are 4 different ways to travel from F to A without repeating stations.

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.

Reading the answer is not the same as getting it right under a clock. Practise this question with UPSC's negative marking, and anything you miss goes into an error notebook until you get it right twice.

Practise this paper free