रहस्यमय गणितीय प्रतिभा और लेखक क्रमचय समस्या के समाधान को बढ़ावा देते हैं

ऑस्ट्रेलियाई विज्ञान कथा लेखक ग्रेग एगन द्वारा लिखित और 2011 के प्रमाण, जो गुमनाम रूप से नेट पर पोस्ट किए गए हैं, इस रहस्य के अध्ययन में महत्वपूर्ण सफलताओं के रूप में पहचाने गए, जो गणितज्ञ 25 वर्षों से शोध कर रहे हैं।

16 सितंबर, 2011 को, एनीमे के प्रशंसक ने मंच पर पंथ श्रृंखला "द मेलानचोली ऑफ हरुही सुजुमिया " पर 4chan गणित प्रश्न पोस्ट किया। शो का पहला सीज़न, जहाँ समय यात्राएँ थीं, कालानुक्रमिक की तुलना में एक अलग क्रम में दिखाया गया था, और बाद के शो और डीवीडी पर रिलीज़ के दौरान, एपिसोड के क्रम को फिर से बदल दिया गया था। इंटरनेट पर, प्रशंसकों ने तर्क दिया कि किस क्रम में श्रृंखला को देखना बेहतर है, और प्रश्न के लेखक ने पूछा: यदि दर्शक श्रृंखला को सभी संभावित आदेशों में देखना चाहते थे, तो उनकी सबसे छोटी सूची में कितने एपिसोड होंगे? [ एक सूची को संदर्भित करता है जिसमें आप एपिसोड / लगभग किसी भी अनुक्रम को पा सकते हैं। ट्रांस। ]

एक घंटे से भी कम समय में, एक अनाम लेखक ने प्रश्न का उत्तर प्रदान किया - एक पूर्ण समाधान नहीं, बल्कि आवश्यक संख्या के एपिसोड पर एक कम बाउंड। उनके तर्क से, किसी भी संख्या के एपिसोड पर लागू होने के बाद, यह हुआ कि हरुही के पहले सीज़न के लिए, जिसमें 14 एपिसोड शामिल थे, दर्शकों को सभी संभावित क्रमों का अध्ययन करने के लिए एक पंक्ति में कम से कम 93,884,313,611 एपिसोड देखने होंगे। "दोषों के लिए सबूतों की जांच करें जो मुझे याद हो सकते हैं," प्रतिक्रिया के लेखक ने लिखा।

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

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

और अब, ह्यूस्टन और पैनटन, फ्लोरिडा विश्वविद्यालय के विंस वेटर के साथ मिलकर एक औपचारिक काम लिखा है। इसमें, उन्होंने पहले लेखक को "अनाम 4chan पोस्टर" के रूप में संकेत दिया।

ह्यूस्टन ने कहा, "अजीब बात यह है कि पहले से मौजूद अज्ञात तथ्य का यह बहुत ही सुंदर सबूत है।"

क्रमपरिवर्तन के शहर

यदि श्रृंखला में केवल तीन एपिसोड हैं, तो उन्हें देखने के छह संभावित तरीके हैं: 123, 132, 213, 231, 312 और 321। उन्हें एक साथ चिपकाया जा सकता है और ऑर्डर के प्रत्येक संस्करण सहित 18 एपिसोड की सूची बना सकते हैं। हालाँकि, एक अधिक कुशल gluing विधि भी है: 123121321. ऐसे अनुक्रम जिसमें n वर्णों के सेट के सभी क्रमपरिवर्तन होते हैं, सुपर-क्रमचय कहलाते हैं।

1993 में, डैनियल एशलॉक और जेनेट टिलोट्सन ने पाया कि n के विभिन्न मूल्यों के लिए सबसे कम सुपर क्रमों का अध्ययन करते समय, तथ्यात्मक तेजी से दिखाई देने लगते हैं - फॉर्म n में लिखे गए समान मान!, अर्थात, उदाहरण के लिए 1 से n तक सभी संख्याओं को गुणा करना (उदाहरण के लिए, 4) ! = ४ * ३ * २ * १)।

यदि आपकी श्रृंखला में केवल 1 प्रकरण है, तो सबसे छोटी सुपर-क्रमचय की लंबाई 1 होगी! (अच्छी पुरानी इकाई के रूप में भी जाना जाता है)। दो एपिसोड की एक श्रृंखला के लिए, सबसे कम सुपर-क्रमचय (121) की लंबाई 2 है! + 1! .. तीन एपिसोड (ऊपर उदाहरण) के लिए, लंबाई 3 है! + 2! + 1!, और चार एपिसोड (123412314231243121342132413214321) के लिए यह 4 होगा! + ३! + 2! + 1! .. तथ्यात्मक नियम आम तौर पर स्वीकार किए जाते हैं (हालांकि कोई भी यह साबित नहीं कर सकता था कि यह सभी n के लिए सच है), और बाद में गणितज्ञों ने n = 5 के लिए इसकी पुष्टि की।

फिर 2014 में, ह्यूस्टन ने गणितज्ञों को प्रभावित किया, यह दिखाते हुए कि n = 6 के लिए शासन ने काम करना बंद कर दिया। नियम यह भविष्यवाणी करता है कि हर संभव तरीके से छह एपिसोड देखने के लिए 873 एपिसोड लेने होंगे, लेकिन ह्यूस्टन ने इसे 872 में करने का एक तरीका पाया। और चूंकि n वर्णों के लिए लघु सुपर क्रमोन्नति को n + 1 वर्ण में बदलने के लिए एक सरल तरीका है, ह्यूस्टन उदाहरण का अर्थ है कि नियम भाज्य सभी n> 6 के लिए काम नहीं करता है।

बिल्डिंग ह्यूस्टन सुपर-परम्यूटेशन के काम को प्रसिद्ध ट्रैवलिंग सेल्समैन समस्या में बदल देता है, जो कई शहरों से होकर सबसे छोटा रास्ता तलाश रहा है। विशेष रूप से, सुपर-परम्यूटेशन "असममित" सेल्समैन समस्या से जुड़े हैं, जिसमें दो शहरों के बीच के प्रत्येक रास्ते की अपनी कीमत है (जरूरी नहीं कि दोनों दिशाओं में समान हो), और लक्ष्य सभी शहरों के माध्यम से सबसे सस्ता रास्ता खोजना है।

यह परिवर्तन समझना आसान है: कल्पना करें कि प्रत्येक क्रमपरिवर्तन एक शहर है, और प्रत्येक क्रमपरिवर्तन से हर दूसरे क्रमपरिवर्तन के लिए पथ की कल्पना करें। सुपर-परम्यूटेशन समस्या में, हमें सबसे कम अनुक्रम अंकों की आवश्यकता होती है, जिसमें सभी क्रमपरिवर्तन मौजूद होते हैं, इसलिए हमारा लक्ष्य सभी क्रमपरिवर्तन से गुजरना है ताकि प्रारंभिक क्रमचय के लिए यथासंभव कुछ संख्याओं को जोड़ा जा सके। हम घोषणा करते हैं कि प्रत्येक पथ की लागत बस अंको की संख्या है जिसे दूसरी प्राप्त करने के लिए हमें पहले क्रमपरिवर्तन के अंत में संलग्न करना होगा। N = 3 के साथ उदाहरण में, 231 से 312 तक के मार्ग की लागत $ 1 है, क्योंकि हमें 312 प्राप्त करने के लिए 231 के अंत में केवल 2 को जोड़ने की आवश्यकता है, और 231 से 132 तक के मार्ग की लागत $ 2 है, क्योंकि हमें 32 को जोड़ने की आवश्यकता है। इस तरह के निर्माण में, सबसे सस्ता तरीका। सभी शहर सीधे सबसे छोटे सुपर-क्रमपरिवर्तन के अनुरूप हैं।



इस तरह के परिवर्तन का मतलब था कि ह्यूस्टन एल्गोरिदम की सभी क्षमताओं को यात्रा-सेल्समैन की समस्या को सुलझाने के लिए सुपर-परमुटेशन समस्या को निर्देशित कर सकता है। यह समस्या एनपी-कॉम्प्लेक्स वालों के वर्ग के लिए जानी जाती है, जिसका अर्थ है एक प्रभावी एल्गोरिदम की अनुपस्थिति जो इसे सामान्य मामले में हल कर सकती है। हालांकि, ऐसे एल्गोरिदम हैं जो प्रभावी रूप से समस्या की कुछ किस्मों को हल कर सकते हैं, और अन्य एल्गोरिदम अच्छे अनुमानित समाधान पैदा कर सकते हैं। ह्यूस्टन ने उत्तरार्द्ध में से एक का उपयोग लंबाई में 872 अंकों के सुपर-क्रमांकन को जारी करने के लिए किया था।

चूंकि उन्होंने केवल एक अनुमानित समाधान दिया था, इसलिए यह सबसे आदर्श सुपर-परम्यूटेशन भी नहीं हो सकता है। पैटन ने कहा कि गणितज्ञ अब कम से कम 6-वर्ण क्रमांकन के लिए एक कम्प्यूटेशनल कम्प्यूटेशनल खोज कर रहे हैं। उन्होंने कहा, "हम जानते हैं कि हमारी खोज एक सीमित समय में समाप्त हो जाएगी, लेकिन हमें नहीं पता कि इसमें एक सप्ताह या एक लाख साल लगेंगे," उन्होंने कहा। "कोई प्रगति पट्टी नहीं है।"

गलत आदेश

जब तक ह्यूस्टन का काम दिखाई दिया, तब तक 4chan पर एक गुमनाम पोस्ट लगभग तीन वर्षों तक उनके इंटरनेट कोने में थी। माउंट मैडिसन यूनिवर्सिटी के एक गणितज्ञ, नाथनियल जॉन्सटन ने इस पोस्ट की एक प्रति एक अन्य साइट पर दिखाई, जिसके कुछ दिन बाद यह पोस्ट सामने आई - और इसलिए कि वह एक एनीमे प्रेमी था, लेकिन क्योंकि उसने Google में विभिन्न अनुरोध दर्ज किए, सुपर-क्रमपरिवर्तन के साथ जुड़ा हुआ है।

जॉनसन ने सबूत पढ़े और यह उनके लिए विश्वसनीय लग रहा था, लेकिन उन्होंने पूरी तरह से परीक्षा में अपनी ऊर्जा बर्बाद नहीं की। उस समय, गणितज्ञों का मानना ​​था कि सुपर-क्रमपरिवर्तन के लिए फैक्टरियल फॉर्मूला सबसे अधिक सही था, और जब आप सोचते हैं कि आप किसी प्रश्न का सटीक उत्तर जानते हैं, तो आप अनुमान के निचले हिस्से में दिलचस्पी नहीं रखते हैं। दूसरे शब्दों में, सुपर-क्रमपरिवर्तन के बारे में श्रृंखला के एपिसोड गलत क्रम में चले गए।

उसके बाद, जॉन्सटन ने एक जोड़ी वेबसाइटों पर निचली सीमा का उल्लेख किया, लेकिन मुझे नहीं लगता कि किसी ने इस पर विशेष ध्यान दिया, "उन्होंने कहा।

फिर, 26 सितंबर, 2018 को, रिवरसाइड में कैलिफोर्निया विश्वविद्यालय के गणितज्ञ जॉन बैज ने ह्यूस्टन की 2014 की खोज के बारे में एक पोस्ट ट्वीट किया, जो स्पष्ट गणितीय पैटर्न के बारे में ट्वीट्स की एक श्रृंखला के हिस्से के रूप में काम करना बंद कर देता है।

लगभग। perev।: ट्वीट्स की इतनी बड़ी श्रृंखला नहीं थी, केवल तीन। अन्य दो भी अपने आप में दिलचस्प हैं, हालांकि वे इस लेख से संबंधित नहीं हैं। एक कहता है कि 6 17,427,000,000,000,000,000,000,000,000,000 से छोटे सभी अपराधों के लिए दो आसन्न अपराधों के बीच सबसे लोकप्रिय दूरी है। और फिर यह पैटर्न अचानक काम करना बंद कर देता है! दूसरा इंटीग्रल्स, त्रिकोणमितीय फ़ंक्शन और संख्या second के निम्नलिखित कनेक्शन को दर्शाता है



लेकिन केवल n <9.8 × 10 ^{42 के लिए} !

उनके ट्वीट ने एगन का ध्यान आकर्षित किया, जिन्होंने कई दशक पहले गणित का अध्ययन किया था, एक मान्यता प्राप्त विज्ञान कथा लेखक के रूप में उनका करियर शुरू होने से पहले (एक भाग्यशाली अवसर द्वारा उनकी पहली सफल कहानी, जिसे "क्रमोन्नति का शहर" कहा जाता था)। ईगन ने मेल में लिखा, "मैं गणित में कभी रूचि नहीं लेना चाहता था।"

इगन ने आश्चर्यचकित किया कि क्या ह्यूस्टन की तुलना में भी कम-से-सुपर-क्रमचय बनाना संभव था। वह क्रमपरिवर्तन के नेटवर्क में शॉर्टकट बनाने के तरीके पर साहित्य के अध्ययन में डूब गए, और कुछ हफ्तों के बाद उन्हें जो चाहिए था, वह मिला। कुछ दिनों में, उन्होंने n वर्णों के सबसे छोटे सुपर-क्रमांकन की लंबाई पर एक नई ऊपरी सीमा काट दी: n! + (n - 1)! + (n - 2)! + (n - 3)! + n - 3. यह तथ्यात्मक सूत्र के समान है, जिसमें से कई सदस्यों को बाहर रखा गया था।

"यह पूरी तरह से पिछले ऊपरी हिस्से को तोड़ दिया," ह्यूस्टन ने कहा।

4chan पर पोस्ट के लेखक की निचली सीमा आकर्षक रूप से नई ऊपरी सीमा के करीब थी: n! + (n - 1)! + (n - 2)! + एन - 3. परिणाम के प्रकाशन के बाद, ईगन जॉनसन ने एक अनाम लेखक के प्रमाण के गणितज्ञों को याद दिलाया, और ह्यूस्टन और पैंटन ने जल्द ही इसकी शुद्धता साबित की। जैसा कि ह्यूस्टन के काम में, नए निचले और ऊपरी सीमाएं यात्रा विक्रेता की समस्या के दृष्टिकोण से सुपर-क्रमपरिवर्तन के अनुकूल हैं: निचली सीमा से पता चलता है कि सभी शहरों के रास्ते $ 1 से अधिक मूल्य के कुछ न्यूनतम मार्गों से गुजरना चाहिए, और ऊपरी सीमा प्रत्येक n के लिए एक विशेष मार्ग बनाती है। केवल $ 1 और $ 2 के यौगिकों का उपयोग करना।

अब, शोधकर्ता ऊपरी और निचली सीमाओं को एक साथ लाने की कोशिश कर रहे हैं, और एक एकल सूत्र खोज रहे हैं जो सुपर-क्रमचय की समस्या को हल करता है। "शायद, अंत में, लोग अभी भी इस पहेली को हल करेंगे," बैज ने भविष्यवाणी की। "अब सब कुछ अच्छा लग रहा है।"

हरुही के प्रशंसकों के लिए, ईगन का समाधान सटीक निर्देश देता है कि कुल 93,924,230,411 का उपयोग करके पहले सीज़न के लिए सभी संभावित विकल्पों को कैसे देखा जाए। आप आज देखना शुरू कर सकते हैं, या आप तब तक इंतजार कर सकते हैं जब तक गणितज्ञ इस संख्या में कटौती नहीं कर सकते। एक अनाम लेखक की निचली सीमा यह साबित करती है कि यह कटौती उन्हें 40 मिलियन से अधिक एपिसोड नहीं बचाएगी - हालांकि, यह दूसरे सत्र की तैयारी शुरू करने के लिए पर्याप्त है।