हमारे पहेली कार्य पिछले महीने एक को बचाने के लिए था स्टार ट्रेक के नेतृत्व में आठ की सतह पार्टी उद्यम संचार अधिकारी लेफ्टिनेंट उहुरास (देर से खेला गया Nichelle निकोल्स) चालक दल को एक ग्रह पर एक विदेशी जाति, कैटेनटी द्वारा कैद किया गया है हार नीहारिका. बचने के लिए, उन्हें उस कार्य को करने की अपनी संभावना को अधिकतम करना होगा जो पहली बार में सफलता की निराशाजनक संभावना प्रदान करता है।
आठ के चालक दल को कार्य के बारे में सूचित किया जाता है जबकि अस्थायी रूप से एक आम कमरे में आयोजित किया जाता है जहां वे संवाद करने और रणनीति बनाने के लिए स्वतंत्र होते हैं। कुछ ही घंटों में, उन्हें रूले चैम्बर नामक एक कमरे में, एक-एक करके ले जाया जाएगा। इस कमरे में एक पंक्ति में आठ बटन हैं, जिनमें से प्रत्येक को एक अलग चालक दल के सदस्य को जवाब देने के लिए प्रोग्राम किया गया है। क्रू को गुमराह करने के लिए, प्रत्येक बटन को किसी अन्य क्रू सदस्य के नाम के साथ बेतरतीब ढंग से गलत लेबल किया जाता है। प्रत्येक चालक दल के सदस्य को किसी भी क्रम में अधिकतम चार बटन दबाने की अनुमति है। जब भी वे एक बटन दबाते हैं, वे देखेंगे कि बटन वास्तव में किसका है। अपने चार प्रयासों के भीतर, उन्हें उन्हें सौंपा गया बटन ढूंढना होता है। चालक दल के मुक्त होने के लिए, उन सभी को इस कार्य में सफल होना है। यदि उनमें से एक भी विफल हो जाता है, तो सभी को मार दिया जाएगा। एक चालक दल के सदस्य द्वारा अपना प्रयास पूरा करने के बाद, उन्हें अपने किसी भी चालक दल के साथी को जानकारी देने का कोई रास्ता नहीं होने के कारण अलग-थलग कर दिया जाता है।
सफलता की संभावना कम नजर आ रही है। यदि चालक दल के सदस्य बेतरतीब ढंग से बटन चुनते हैं, तो प्रत्येक के पास अपना बटन खोजने का 1 से 2 मौका होगा। सभी आठ के सफल होने की संभावना 1 में से केवल 256 या लगभग 0.4% है।
लेकिन उन्हें बेतरतीब ढंग से बटन दबाने की जरूरत नहीं है। सफलता की संभावना को बढ़ाने का एक तरीका यह हो सकता है कि किसी भी तरह से सभी बटन दबाए जाएं। यह हमें हमारे पहले पहेली प्रश्न पर लाता है।
1 पहेली
चालक दल के जीवित रहने की संभावना में कितना सुधार हो सकता है यदि वे यह सुनिश्चित करते हैं कि प्रत्येक बटन को समान रूप से बार-बार दबाया जाए (बजाय किसी चार बटन को बेतरतीब ढंग से दबाने के)?
रोब कोर्लेट और जेपीएट इसका अच्छी तरह से उत्तर दिया, जैसा कि उन्होंने अन्य सभी प्रश्नों का उत्तर दिया। इस कॉलम में पहेली के पीछे छिपे केंद्रीय विचार के लिए, रोब कॉर्लेट, जेपीएट और जौनी सेप्पनेनी इसे खूबसूरती से वर्णित किया, जबकि सच्चा बुग्नन कंप्यूटर समाधान में योगदान दिया।
रोब कॉर्लेट का जवाब यहां दिया गया है:
यह सुनिश्चित करने का एक तरीका है कि प्रत्येक बटन को समान संख्या में दबाया जाए, कैदियों को 4 के दो समान आकार के समूहों में अलग करना है।
प्रत्येक समूह केवल अपने समूह के सदस्यों के अनुरूप बटन दबाता है। इस प्रकार, यदि ए, बी, सी और डी सभी एक ही उपसमूह में हैं तो वे केवल ए, बी, सी और डी के लिए बटन दबाते हैं।
यह समस्या को इस संभावना में बदल देता है कि प्रत्येक कैदी को सही समूह में आवंटित किया जाता है, तब उन्हें चार या उससे कम प्रेस में अपना बटन दबाने की गारंटी दी जाती है।
चार लोगों के साथ पहले समूह (और इसलिए दूसरा समूह भी) को भरने के तरीकों की संख्या 4 में से 8 चुनने के तरीकों की संख्या है जो सी (8, 4) = 70 है। इसलिए, कुल तरीकों की संख्या सभी को दो समूहों में आवंटित करना 70 है।
केवल एक आवंटन है जो प्रत्येक कैदी को सही समूह में सही ढंग से आवंटित करता है और इसलिए सभी के सही समूह में होने और सभी कैदियों के जीवित रहने की संभावना 1/70 है जो पिछली रणनीति के 3.66/1 से 256 गुना बेहतर है। [लेकिन यह अभी भी बहुत छोटा है: केवल 1.4% मौका।]
2 पहेली
मूल निराशाजनक बाधाओं को 90-गुना से बढ़ाकर लगभग 36.5% करने का एक तरीका है, जो चमत्कारी लगता है! इस रणनीति में लूप या अनुमानों की जंजीरों का उपयोग शामिल है - इसलिए नेकलेस नेबुला और कैटेनटी के संदर्भ (श्रृंखला चेन के लिए लैटिन है)। रणनीति के मूल रूप में, प्रत्येक क्रू मेंबर अपने नाम वाले बटन को दबाकर शुरू करता है, फिर क्रू मेंबर के नाम वाले बटन पर जाता है, जो वास्तव में पहला बटन था, और इसी तरह, नामों की एक श्रृंखला बनाता है।
आइए देखें कि यह व्यवहार में कैसे काम करता है। आरेख में, बटन सफेद रंग में उनके लेबल के साथ दिखाए जाते हैं। नीचे दिए गए नीले अक्षर बटनों के वास्तविक स्वामी को दर्शाते हैं। जब चालक दल का पहला सदस्य, A, रूले कक्ष में प्रवेश करता है, तो वह पहले बटन A दबाती है। यह सी का बटन है, इसलिए वह आगे बटन सी दबाती है, फिर बटन ई और अंत में एफ बटन दबाती है, जो वास्तव में ए का अपना बटन है, इसलिए उसने इसे चार प्रयासों में सफलतापूर्वक पाया है। ध्यान दें कि ACEF बटन चार बटनों का एक बंद लूप बनाते हैं। जब चालक दल के सदस्य सी, ई और एफ अपनी बारी लेते हैं, तो वे भी उसी बंद लूप के चारों ओर जाएंगे, जो अपने-अपने स्थानों से शुरू होगा, और चार प्रयासों में अपने स्वयं के बटन भी ढूंढेंगे।
इस व्यवस्था में दो-दो बटनों के दो छोटे लूप भी हैं: बीडी और जीएच। चालक दल के इन चार सदस्यों को दो कोशिशों के भीतर अपने स्वयं के बटन मिल जाएंगे। तो, इस व्यवस्था के साथ, सभी चालक दल के सदस्य सफल होंगे, और उन्होंने अपनी स्वतंत्रता अर्जित की होगी। यह स्पष्ट है कि यदि व्यवस्था में केवल 4 या उससे कम लंबाई के लूप होते हैं, तो चालक दल के सभी सदस्य सफल होंगे और मुक्त हो जाएंगे। यदि, दूसरी ओर, 5 या अधिक का एकल लूप है, तो उस लूप के सभी चालक दल के सदस्य चार प्रयासों में अपना बटन खोजने में विफल होंगे, और चालक दल को निष्पादित किया जाएगा। सफलता की प्रायिकता ज्ञात करने के लिए, हम 5, 6, 7 या 8 के लूप होने की प्रायिकता ज्ञात कर सकते हैं, उन्हें जोड़ सकते हैं, और उस योग को 1 से घटा सकते हैं। यह अन्य तरीकों की तुलना में गणना करना आसान है क्योंकि आठ के लिए बटन, केवल एक ही लूप हो सकता है जिसमें 5, 6, 7 या 8 सदस्य हों।
8 हैं! आठ बटनों को व्यवस्थित करने के विभिन्न तरीके। लेकिन जब हम लूप बनाते हैं, तो एक ही लूप इन आठ व्यवस्थाओं के लिए जिम्मेदार होता है (ABCDEFGH, BCDEFGHA के समान लूप बनाता है, जो कि CDEFGHAB, आदि के समान है)। तो आकार 8 का लूप होने की संभावना (8!/8)/8! है, जो कि केवल 1/8 है। इसी तरह, आकार 7 का लूप होने की संभावना 1/7 है, आकार 6 का 1/6 है, और आकार 5 का 1/5 है। इसलिए, हमारे निडर दल के लिए सफलता की संभावना 1 - (1/5 + 1/6 + 1/7 + 1/8), या 36.5% है, जैसा कि पहले उल्लेख किया गया है।
उपरोक्त रणनीति किसी भी संख्या में कैदियों के लिए काम करती है, और यादृच्छिक दृष्टिकोण पर बाधाओं में सुधार तेजी से बढ़ता है क्योंकि यह संख्या बढ़ती है। यह चार कैदियों के लिए लगभग सात गुना, छह के लिए 24 गुना, आठ के लिए 93 गुना और आश्चर्यजनक (3.8 × 10) है।29) - 100 कैदियों के लिए गुना। इस भारी वृद्धि को समझने की कुंजी यह है कि यह विधि समूह के प्रत्येक सदस्य की सफलता या विफलता को दूसरों के साथ बांधती है। काफी हद तक, वे सभी एक साथ सफल या असफल होते हैं। समूह की सफलता की संभावना एक व्यक्ति की तुलना में बहुत अधिक कम नहीं होती है, एक कैदी के लिए केवल 50% से गिरकर 30.69% हो जाती है क्योंकि कैदियों की संख्या बिना सीमा के बढ़ जाती है। दूसरी ओर, एक यादृच्छिक दृष्टिकोण या यहां तक कि एक "सम-बटन प्रेस" दृष्टिकोण के सफल होने की संभावना भी कैदियों की एक छोटी संख्या के लिए भी शून्य के बहुत करीब तक तेजी से घट जाती है।
यदि इस रणनीति के पीछे तर्क अभी भी अस्पष्ट लगता है, तो यहां 100-कैदी की समस्या का विश्लेषण किया गया है Veritasium द्वारा उत्कृष्ट वीडियो.
3 पहेली
यह पहेली लेफ्टिनेंट उहुरा के बचपन के खेल को याद करने के बारे में थी, जो अनिवार्य रूप से एक ही पहेली थी, लेकिन छह लोगों के लिए। एक संकेत के रूप में, मैंने चार लोगों के लिए समस्या का समाधान करने का सुझाव दिया। अब जब हमारे पास सूत्र है, तो हम आसानी से संभावनाओं की गणना कर सकते हैं।
चार लोगों के लिए, सबसे लंबा लूप सिर्फ 2 या 1 होने की संभावना है: 1 - (1/3 + 1/4) या 41.7% यादृच्छिक पसंद पर सात गुना लाभ के साथ।
छह लोगों के लिए, सबसे लंबा लूप 3, 2 या 1 होने की प्रायिकता है: 1 - (1/4 + 1/5 + 1/6) या 38.3% यादृच्छिक पसंद पर 24 गुना से अधिक लाभ के साथ।
4 पहेली
जैसा कि हमारी कहानी जारी है, यह पता चला है कि कैटेनटी में से एक ने विशेष नापसंद किया है उद्यम चालक दल और दूर से उनकी निगरानी कर रहा है। उन्हें संदेह है कि वे उहुरा के आरेख के आधार पर कुछ प्रभावी रणनीति लेकर आए हैं। वह कक्ष में फिसल कर और रूले शुरू होने से पहले जानबूझकर बटन लेबल के क्रम को बदलकर उनकी योजना को विफल करने के लिए दृढ़ संकल्पित है। क्या वह योजना को सफलतापूर्वक विफल कर सकता है? लैंडिंग पार्टी को छुपाने के लिए विशेष रूप से सावधान रहने की क्या ज़रूरत है?
चालक दल की रणनीति चर्चा में बहुत पहले, उहुरा की आँखें अचानक संकुचित हो गईं। उसने अपने चालक दल को एक संकेत दिया, और उसने घोषणा करते हुए, "निकोलीज़ में आगे की सभी चर्चा, कृपया।" निकोलीज़ एक नई भाषा थी, जिसका आविष्कार उहुरा ने अपने करियर की शुरुआत में ही इस तरह की स्थिति के लिए, सार्वभौमिक अनुवादकों के उपयोग को रोकने के लिए किया था। "आपने देखा होगा कि संदिग्ध Catenati," उसने जारी रखा। "वह हमें तोड़फोड़ करने की कोशिश कर सकता है, इसलिए हमें अपनी योजना को संशोधित करने की आवश्यकता है। यहाँ हमें क्या करना है… ”
उहुरा ने नई योजना को तब तक रेखांकित किया जब तक कि वह संतुष्ट नहीं हो गई कि उसके दल का प्रत्येक सदस्य इसे पूरी तरह से जानता था। फिर उसने अपनी आँखों में एक दूर की नज़र के साथ कहा, "मैंने 20 वीं सदी की एक प्रतिष्ठित अभिनेत्री के नाम पर निकोलीज़ का नाम रखा। मुझे खुशी है कि मैंने जोर देकर कहा कि Starfleet हमारे सभी जहाजों पर इसे मानक बनाए। ”
वह वापस चालक दल में बदल गई। "बस इतना ही, अधिकारियों। तुम जानते हो कि तुम्हें क्या करना है!"
हम ठीक से नहीं जानते कि उहुरा ने अपनी टीम को क्या बताया। लेकिन JPayette और Rob Corlett का विचार बहुत अच्छा था। यहाँ रोब कॉर्लेट फिर से है:
यदि दुष्ट कैटेनाटी सुनता है कि वे इस रणनीति को नियोजित कर रहे हैं तो वह यह सुनिश्चित करने के लिए प्रदर्शन पर दिखाए गए नामों को बदल सकता है कि एक चक्र 4 से अधिक लंबा है।
इसे तोड़ने के लिए कैदियों को एक गुप्त आदेश के लिए सहमत होने की आवश्यकता होती है जो अनुक्रम को यादृच्छिक बनाता है। वे ऐसा कुछ कहकर करते हैं, "यदि आप उहुरा का नाम देखते हैं, तो चेकोव चिह्नित बटन पर जाएं। यदि आप चेकोव का नाम प्रदर्शित करते हुए देखते हैं, तो स्मिथ, आदि के रूप में चिह्नित बटन पर जाएं।
इस तरह, कैटेनटी द्वारा पुन: क्रमित करना कोई मायने नहीं रखता क्योंकि यह केवल तभी काम करता है जब आप उस तरीके को जानते हैं जिसमें चालक दल डिस्प्ले पर नामों का जवाब देगा। हालांकि उन्हें किसी भी पुनर्क्रमण को गुप्त रखने की आवश्यकता है, अन्यथा इसे फिर से तोड़ा जा सकता है।
जैसा कि हमने देखा, उहुरा ने सुनिश्चित किया कि रहस्य को सुरक्षित रखा जाएगा। चालक दल के प्रत्येक सदस्य को बस उसी गुप्त आदेश का उपयोग करने और यह सुनिश्चित करने की आवश्यकता थी कि दुष्ट कैटेनती को यह नहीं पता था कि यह क्या था। वास्तव में, दुष्ट कैटेनती द्वारा बदले गए आदेश ने वास्तव में चालक दल के सफल होने की संभावना को बढ़ा दिया!
यह हुआ था। उहुरा को सबसे पहले रूले चैंबर में ले जाया गया था। उसने तीन बटन दबाए। कोई उसका नहीं था। क्या उसे दुखी होना चाहिए या खुश होना चाहिए? उसने अपनी सांस रोककर चौथा दबाया। उसे अपना असली बटन मिल गया था!
वह जानती थी कि वे सभी बच जाएंगे।
5 पहेली
जैसे-जैसे लैंडिंग पार्टी का आकार अनिश्चित काल के लिए बढ़ता है, सफलता का अधिकतम प्रतिशत किस सीमा तक पहुंचता है? क्या आप बता सकते हैं कि यादृच्छिक बटन दबाने की तुलना में यह विधि इतनी अधिक कुशल क्यों है?
जेपीएट ने लिखा:
उपरोक्त सभी 2 . के दल के लिए सीधे सामान्यीकरण करते हैंn सदस्यों को अधिक से अधिक प्रेस करने की अनुमति है n बटन। पहेली 2 से, हम यह निष्कर्ष निकालते हैं कि उनकी सफलता की संभावना है
1 - (योग से अधिक k के बीच n + 1 और 2n १०/k).
योग की तुलना 1/ के समाकल से की जा सकती हैx अंतराल पर [n, 2n], जो हमें यह साबित करने की अनुमति देता है कि n अनंत तक बढ़ता है, तो उपरोक्त संभावना घट कर एक आश्चर्यजनक 1 - ln(2) 30.6% में परिवर्तित हो जाती है। [वास्तव में 30.69% से दो दशमलव स्थानों तक।]
रोब कॉर्लेट ने कहा:
यदि आप एकीकरण नहीं जानते हैं, तो आप स्प्रैडशीट का उपयोग करके गणना करके शीघ्रता से अनुमानित उत्तर प्राप्त कर सकते हैं। मुझे एक बार 0.307 मिल गया n लगभग 750 तक पहुंच गया जो 3 दशमलव स्थानों तक सटीक है।
हम पहले ही ऊपर बता चुके हैं कि यह तरीका क्यों काम करता है। 1 से अधिक लंबे सभी लूप कई क्रू सदस्यों द्वारा साझा किए जाते हैं। इसलिए उनकी सफलता और असफलता अत्यधिक सहसंबद्ध हैं। यह "सभी के लिए एक, और सभी के लिए एक" सिद्धांत का एक उदाहरण है। Starfleet मैनुअल से सीधे बाहर!
हमारे सभी योगदानकर्ताओं को धन्यवाद। JPayette और Rob Corlett दोनों ने बेशकीमती जवाब प्रस्तुत किए जिससे यह समाधान कॉलम लगभग बेमानी लग रहा था। काश, मुझे प्रति पहेली कॉलम में एक विजेता चुनने के हमारे नियम पर टिके रहना चाहिए। इनसाइट्स पुरस्कार यहां और पिछली पहेली में योगदान की मान्यता में JPayette को जाता है। बधाई हो! रोब कॉर्लेट, आपके योगदान को भुलाया नहीं जा सकेगा।
नई जानकारी के लिए अगले महीने मिलते हैं!
