Some Generalizations of the Bridge and Torch Problem

कल्पना कीजिए कि एक ऐसी दुनिया जहाँ सबसे रोमांचक पहेलियाँ छिपे हुए खजाने को खोजने या किसी हत्या की गुत्थी सुलझाने के बारे में नहीं हैं, बल्कि अपने दोस्तों के एक समूह को सूरज उगने से पहले एक अंधेरे, जर्जर पुल से पार कराने के बारे में हैं। यह कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन (combinatorial optimization) का क्षेत्र है, जो गणित की एक शाखा है जो पूछती है: "जब आपके पास सख्त नियम हों, तो कुछ करने का सबसे अच्छा तरीका क्या है?" इसे टेट्रिस (Tetris) के परम खेल के रूप में सोचें, लेकिन ब्लॉकों के बजाय, आप लोगों को समय के स्लॉट में फिट कर रहे हैं, और लक्ष्य सबसे कम समय में स्तर को पूरा करना है। इस खेल का क्लासिक संस्करण, जिसे "ब्रिज एंड टॉर्च प्रॉब्लम" (Bridge and Torch Problem) के रूप में जाना जाता है, अपने धोखेबाज रूप से सरल नियमों के लिए प्रसिद्ध है: लोगों के एक समूह को रात में केवल एक टॉर्च के साथ एक पुल पार करना होगा। पुल संकरा है (एक बार में केवल दो लोग आ सकते हैं), टॉर्च हर बार किसी के पार जाने पर साथ ले जानी होगी, और यदि दो लोग एक साथ चलते हैं, तो वे धीमे व्यक्ति की गति से चलेंगे। यह सुनने में आसान लगता है, लेकिन सबसे तेज़ शेड्यूल ढूंढना समय और रणनीति का एक जटिल नृत्य है जिसने कई लोगों को उलझा दिया है।

अब, उसी पहेली को लेकर उसके स्तर को बढ़ाने की कल्पना करें। क्या होगा यदि पुल तीन लोगों को समा सके? या क्या होगा यदि, एक एकल पुल के बजाय, आपके पास कई स्पोक्स (spokes) वाला एक हब हो, जैसे कि एक मकड़ी का जाल, जहाँ लोग एक ही समय में विभिन्न गंतव्यों तक जा सकें? थंग पांग एर्न (Thang Pang Ern) और जेरार्ड सायसन (Gerard Sayson) ने अपने शोध पत्र में बिल्कुल यही किया। उन्होंने क्लासिक "दो-व्यक्ति वाले पुल" की पहेली को लिया, जहाँ प्रत्येक व्यक्ति का पार होने का समय 1 से $n$ तक होता है, और उन्होंने न केवल इसे हल किया; बल्कि उन्होंने एक जादुई सूत्र भी खोज निकाला जो किसी भी संख्या में लोगों के लिए आवश्यक सटीक न्यूनतम समय की भविष्यवाणी करता है। फिर, उन्होंने सीमाओं को और आगे बढ़ाया, तीन लोगों को समाने वाले पुल के लिए नियम निर्धारित किए, और यहाँ तक कि एक स्टार-आकार के नेटवर्क के लिए भी। उन्होंने पाया कि हालांकि उत्तर जटिल होते जा रहे हैं, वे सुंदर, दोहराते हुए पैटर्न का पालन करते हैं जिन्हें एक एकल समीकरण में लिखा जा सकता है।

क्लासिक टू-पर्सन डांस

आइए मूल पहेली से शुरुआत करें। आपके पास $n$ लोगों का एक समूह है, और उनके पार होने का समय $1, 2, 3, \dots, n$ है। समय 1 वाला व्यक्ति एक धावक है, जबकि समय $n$ वाला व्यक्ति एक सुस्त व्यक्ति है। लक्ष्य सभी को नदी के बाएं किनारे से दाएं किनारे तक पहुँचाना है।

लेखकों ने सिद्ध किया कि इस विशिष्ट सेटअप के लिए, $T(n)$ यानी न्यूनतम समय की गणना करने के लिए एक सटीक, क्लोज्ड-फॉर्म (closed-form) सूत्र मौजूद है। यह केवल एक अनुमान नहीं है; उन्होंने इसे छोटे हिस्सों में तोड़कर निकाला है। उन्होंने महसूस किया कि सर्वोत्तम रणनीति में दो सबसे तेज़ लोगों (1 और 2) को पहले भेजना, उनमें से एक को टॉर्च के साथ वापस भेजना, दो सबसे धीमे लोगों को एक साथ भेजना, और फिर दूसरे तेज़ व्यक्ति को वापस भेजना शामिल है। यह चालों का "ब्लॉक" दो सबसे धीमे लोगों को बाहर निकाल देता है और शेष समूह के लिए प्रक्रिया को दोहराने के लिए सिस्टम को तैयार कर देता है।

इन ब्लॉक्स की लागत को जोड़कर, उन्होंने पाया कि $n$ लोगों के लिए कुल समय है:
$$T(n) = \frac{n^2}{4} + 3n - \frac{5 + (-1)^n - 1}{8}$$
यह सूत्र $n \ge 2$ के लिए प्रत्येक संख्या $n$ के लिए काम करता है। उन्होंने यह भी नोट किया कि उनके द्वारा उत्पन्न समय का क्रम (1, 2, 6, 11, ...) गणित की दुनिया में एक ज्ञात पैटर्न है, लेकिन उन्होंने एक नया, सीधा प्रमाण प्रदान किया कि यह विशिष्ट सूत्र क्यों काम करता है। दिलचस्प बात यह है कि उन्होंने दिखाया कि केवल सबसे तेज़ व्यक्ति को हर किसी के साथ बार-बार भेजने की "मानक" रणनीति हमेशा सबसे अच्छी नहीं होती है। उदाहरण के लिए, 4 लोगों के साथ, मानक तरीका चतुर "ब्लॉक" विधि की तुलना में अधिक समय लेता है।

वह पुल जो तीन लोगों को समा सकता है

इसके बाद, लेखकों ने पूछा: "क्या होगा यदि पुल चौड़ा हो?" उन्होंने कल्पना की कि एक पुल जो एक बार में 3 लोगों तक समा सकता है, लेकिन अभी भी उसमें केवल एक टॉर्च है। यह खेल को पूरी तरह से बदल देता है। तीन लोगों के साथ, आप एक तिकड़ी को भेज सकते हैं, लेकिन आपको अभी भी किसी को रोशनी वापस लाने की आवश्यकता होगी।

उन्होंने पाया कि इस "क्षमता 3" वाले संस्करण के लिए, अनुकूलतम समय, $T_3(n)$, एक अलग, अधिक जटिल लय का पालन करता है। सूत्र में एक द्विघात वक्र (quadratic curve, जैसे $n^2/6$) और कोसाइन (cosine) और $(-1)^n$ वाले कुछ लहरदार पद शामिल हैं। विशेष रूप से, $n \ge 7$ के लिए, समय है:
$$T_3(n) = \frac{n^2}{6} + 2n - \frac{181}{36} + \frac{(-1)^n}{4} - \frac{2}{9} \cos\left(\frac{2n\pi}{3}\right)$$
यह सूत्र इतना अनूठा है कि इसने ऑनलाइन एनसाइक्लोपीडिया ऑफ इंटीजर सीक्वेंसेस (A392834) में एक बिल्कुल नई अनुक्रम संख्या बनाई। लेखों ने यह सिद्ध किया कि सर्वोत्तम रणनीति छह लोगों के समूहों को एक विशिष्ट चक्र में एक बार में स्थानांतरित करने में निहित है, जिससे समस्या $n$ लोगों से $n-6$ लोगों में एक अनुमानित लागत के साथ बदल जाती है। उन्होंने यह सुनिश्चित करने के लिए ब्रूट फोर्स (brute force) द्वारा छोटे नंबरों (जैसे 1 से 6) की भी जाँच की कि सूत्र शुरुआत में सही बैठता है।

उन्होंने संक्षिप्त में एक ऐसे पुल को देखा जो 4 लोगों को समा सकता है, लेकिन उन्होंने स्वीकार किया कि पैटर्न बहुत जटिल हो जाता है और वे अभी तक इसके लिए एक सरल सूत्र नहीं खोज पाए हैं। उन्हें संदेह है कि एक सूत्र मौजूद है, लेकिन यह ढूँढना बहुत कठिन है।

स्टार-शेप्ड नेटवर्क

अंत में, यह शोध पत्र एक एकल पुल से एक विशाल छलांग लगाता है। कल्पना कीजिए कि एक केंद्रीय हब (जैसे रेलवे स्टेशन) है जिसमें कई सड़कें (स्पोक्स) बाहर विभिन्न गंतव्यों (leaves) की ओर जाती हैं। इसे "स्टार ग्राफ" कहा जाता है। इस संस्करण में, आपके पास केंद्र में $n$ लोग हैं, $k$ सड़कें हैं, और $t$ टॉर्च हैं।

यहाँ नियम थोड़े अलग हैं: एक "चरण" में, आप अलग-अलग सड़कों पर लोगों को एक ही समय में भेज सकते हैं, जब तक कि दो लोग एक ही सड़क का उपयोग न करें और कोई भी व्यक्ति एक ही समय में दो स्थानों पर न हो। उस चरण के लिए समय उस व्यक्ति द्वारा निर्धारित होता है जो उस चरण में सबसे धीमा चल रहा है।

लेखकों ने पाया कि न्यूनतम समय इस बात पर बहुत अधिक निर्भर करता है कि आपके पास कितने टॉर्च और कितनी सड़कें हैं। यदि आपके पास एक बड़े विस्फोट में सभी को बाहर भेजने के लिए पर्याप्त टॉर्च और सड़कें हैं, तो समय केवल सबसे धीमे व्यक्ति का समय ($n$) होता है। लेकिन यदि आप सीमित हैं, तो समय लगभग $n^2$ की तरह बढ़ता है। उन्होंने एक निचली सीमा (lower bound) का सूत्र निकाला है:
$$T(n, k, t) \ge sn - ms(s-1)$$
जहाँ $m$ सड़कों या टॉर्च की संख्या में से छोटी संख्या है, और $s$ उन "राउंड्स" की संख्या है जो सभी को बाहर निकालने के लिए आवश्यक हैं।

इस खंड का सबसे शानदार हिस्सा यह है कि यह शुद्ध गणित से कैसे जुड़ता है। जब उन्होंने स्टार-ग्राफ समस्या के लिए संख्याओं को देखा, तो उन्होंने महसूस किया कि वे "फ्लोर फंक्शन" (floor function - जिसका अर्थ है निकटतम पूर्ण संख्या तक नीचे की ओर पूर्णांकित करना) से जुड़ी प्रसिद्ध गणितीय पहचानों को फिर से बना रहे थे। उदाहरण के लिए, विशिष्ट संख्या में लोगों और सड़कों के लिए पहेली को हल करके, उन्होंने फ्लोर फंक्शन के योग के बारे में एक ज्ञात पहचान को "पुनः खोजा", जिससे यह पता चला कि कैसे एक मज़ेदार शेड्यूलिंग पहेली संख्या पैटर्न के गहरे सत्यों को प्रकट कर सकती है।

संक्षेप में, यह शोध पत्र एक क्लासिक पहेली को लेता है, उसे एक सटीक सूत्र के साथ हल करता है, उसे चौड़े पुलों तक विस्तारित करता है, और फिर इसे बहु-पथ नेटवर्क में बदल देता है, और इस पूरी प्रक्रिया के दौरान छिपी हुई गणितीय सुंदरता को उजागर करता है। यह दिखाता है कि एक साधारण पुल पार करने के खेल में भी, रणनीति और संरचना की कई परतें खोजी जा सकती हैं।