आठ रेलवे स्टेशन A, B, C, D, E, F, G और H या तो दो-तरफा मार्गों या एक-तरफा मार्गों से जुड़े हैं। एक-तरफा मार्ग C से A तक, E से G तक, B से F तक, D से H तक, G से C तक, E से C तक और H से G तक हैं। दो-तरफा मार्ग A और E के बीच, G और B के बीच, F और D के बीच तथा E और D के बीच हैं।
कोई रेलगाड़ी F से A तक किसी स्टेशन को बिना एक बार से अधिक पार किए कितने विभिन्न प्रकार से जा सकती है?
सही उत्तर: 4
F से A तक किसी भी स्टेशन को दोहराए बिना जाने वाले विभिन्न मार्गों की संख्या ज्ञात करने के लिए हम F से शुरू करते हैं। चूँकि B और F के बीच का मार्ग केवल B से F की ओर एक-तरफा है, इसलिए हम F से B नहीं जा सकते। अतः F से एकमात्र निकास मार्ग D (दो-तरफा मार्ग F-D द्वारा) है। D से हम या तो E (D-E द्वारा) जा सकते हैं या H (D से H द्वारा) जा सकते हैं। स्थिति 1: यदि हम D से H जाते हैं, तो मार्ग H से G और फिर G से C होगा (क्योंकि G से B जाने पर F पर मार्ग समाप्त हो जाता है)। C से हम A पहुँचेंगे। इससे मार्ग 1 प्राप्त होता है: F से D से H से G से C से A। स्थिति 2: यदि हम D से E जाते हैं, तो E से हमारे पास तीन विकल्प हैं: (क) सीधे E-A द्वारा A (मार्ग 2: F से D से E से A); (ख) E से C और फिर C से A (मार्ग 3: F से D से E से C से A); (ग) E से G, फिर G से C, और अंत में C से A (मार्ग 4: F से D से E से G से C से A)। इस प्रकार, कुल 4 भिन्न मार्ग उपलब्ध हैं। अतः विकल्प D सही है।
In English (Question & Model Answer)
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?
Correct Option: 4
To find the number of unique paths from F to A without repeating any station, we trace the routes starting from F. Since the passage between B and F is one-way from B to F, we cannot go from F to B. Thus, the only exit from F is to D via the two-way passage F-D. From D, we can go to E (via D-E) or H (via D to H). Case 1: If we go from D to H, the only route is H to G, and then G to C (since G to B leads to a dead end at F). From C, we go to A. This gives Path 1: F to D to H to G to C to A. Case 2: If we go from D to E, we have three choices from E: (a) Directly to A via E-A (Path 2: F to D to E to A); (b) To C via E to C, then C to A (Path 3: F to D to E to C to A); (c) To G via E to G, then G to C, then C to A (Path 4: F to D to E to G to C to A). Thus, there are exactly 4 distinct paths. Hence, Option D is the correct answer.