Map folding
पेपर फोल्डिंग के गणित में, मैप फोल्डिंग और स्टाम्प फोल्डिंग कागज के एक टुकड़े को मोड़ने के तरीकों की संख्या को गिनने की दो समस्याएं हैं। स्टाम्प फोल्डिंग समस्या में, कागज टिकटों की एक पट्टी होती है जिसके बीच क्रीज़ होती है, और फोल्ड्स को क्रीज़ पर होना चाहिए। नक्शे के तह की समस्या में, कागज एक नक्शा है, जिसे क्रीज़ द्वारा आयत में विभाजित किया जाता है, और फोल्ड को फिर से केवल इन क्रीज़ के साथ होना चाहिए। डाक टिकट मोड़ने की समस्या के आविष्कार का श्रेय एमिल लेमोइन को दिया जाता है। कई अन्य प्रारंभिक संदर्भ प्रदान करता है। लेबल वाले डाक टिकट डाक टिकट मोड़ने की समस्या में, मोड़ने के लिए कागज वर्गाकार या आयताकार डाक टिकटों की एक पट्टी होती है, जिसे क्रीज द्वारा अलग किया जाता है, और डाक टिकटों को केवल उन क्रीज के साथ मोड़ा जा सकता है। समस्या के एक सामान्य रूप से माने जाने वाले संस्करण में, प्रत्येक डाक टिकट को एक दूसरे के डाक टिकट से अलग माना जाता है, इसलिए डाक टिकटों की एक पट्टी के दो तहों को केवल तभी समतुल्य माना जाता है जब उनके पास डाक टिकटों का समान ऊर्ध्वाधर अनुक्रम हो। उदाहरण के लिए, तीन अलग-अलग टिकटों की एक पट्टी को मोड़ने के छह तरीके हैंः इनमें टिकटों के सभी छह क्रमपरिवर्तन शामिल हैं, लेकिन तीन से अधिक टिकटों के लिए सभी क्रमपरिवर्तन संभव नहीं हैं। यदि, एक क्रमपरिवर्तन के लिए, दो संख्याएँ हैं और एक ही समानता के साथ ऐसी हैं कि चार संख्याएँ,,, और उस चक्रीय क्रम में दिखाई देती हैं, तो उन्हें मोड़ा नहीं जा सकता है। समानता की स्थिति का तात्पर्य है कि डाक टिकटों और डाक टिकटों के बीच और डाक टिकटों और डाक टिकटों के बीच की क्रीज मुड़े हुए डाक टिकटों के ढेर के एक ही तरफ दिखाई देती हैं, लेकिन चक्रीय क्रम की स्थिति का तात्पर्य है कि ये दोनों क्रीज एक दूसरे को पार करते हैं, जो एक भौतिक असंभवता है। उदाहरण के लिए, चार-तत्व क्रमपरिवर्तन 1324 को मुड़ा नहीं जा सकता है, क्योंकि इसमें और के साथ यह वर्जित पैटर्न है। इस पैटर्न के बिना सभी शेष क्रमपरिवर्तनों को मोड़ दिया जा सकता है। डाक टिकटों की एक पट्टी को मोड़ने के विभिन्न तरीकों की संख्या अनुक्रम 1,2,6,16,50,144,462,1392,4536,14060,46310,146376,485914,1557892,5202690 द्वारा दी गई है। ये संख्याएँ हमेशा (क्योंकि एक फोल्डेबल स्टाम्प अनुक्रम का एक चक्रीय क्रमपरिवर्तन हमेशा अपने आप में फोल्डेबल होता है) से विभाज्य होती हैं, और इस विभाजन के भाग 1,1,2,4,10,24,66,174,504,1406,4210,12198,37378,111278,346846,1053874, हैं, जो कि एक अर्ध-अनंत वक्र एक रेखा के साथ क्रॉसिंग कर सकता है, जिसे "सेमीमेंडर" कहा जाता है। ये घुमावदार से निकटता से संबंधित हैं, एक बंद वक्र के लिए एक रेखा के साथ समान संख्या में पार करने के तरीके। मेन्डर स्टाम्प-फोल्डिंग समस्या के समाधान के अनुरूप होते हैं जिसमें पहले और अंतिम स्टाम्प को एक दूसरे से जोड़ा जा सकता है ताकि स्टाम्पों का एक निरंतर लूप बनाया जा सके। 1960 के दशक में, जॉन ई. कोहलर और डब्ल्यू. एफ. लूनन ने एल्गोरिदम को लागू किया, जो उस समय 28 टिकटों के लिए इन संख्याओं की गणना कर सकते थे। अतिरिक्त शोध के बावजूद, इन संख्याओं की गणना करने के लिए ज्ञात विधियों के कार्य के रूप में घातीय समय लगता है। इस प्रकार, ऐसा कोई सूत्र या कुशल एल्गोरिथ्म ज्ञात नहीं है जो इस अनुक्रम को बहुत बड़े मानों तक बढ़ा सके। फिर भी, इस अनुक्रम की घातीय वृद्धि की दर का अनुमान लगाने के लिए भौतिकी से शोध विधियों का उपयोग किया जा सकता है। डाक टिकट मोड़ने की समस्या आमतौर पर डाक टिकटों की पट्टी की केवल संभावित मोड़ने की स्थिति की संख्या पर विचार करती है, इस बात पर विचार किए बिना कि क्या डाक टिकटों की एक खुली हुई पट्टी से शुरू होने वाली चालों के अनुक्रम द्वारा भौतिक रूप से तह का निर्माण करना संभव है। हालांकि, बढ़ई के नियम की समस्या के समाधान के अनुसार, हर मुड़े हुए राज्य का निर्माण किया जा सकता है (या समकक्ष रूप से, खुलासा किया जा सकता है)। स्टाम्प फोल्डिंग समस्या के एक अन्य संस्करण में, स्टाम्प की पट्टी को खाली माना जाता है, ताकि इसके एक छोर को दूसरे से बताना संभव न हो, और दो फोल्डिंग को केवल तभी अलग माना जाता है जब उनके अलग-अलग आकार हों। एक मुड़ी हुई पट्टी को ऊपर-नीचे या पीछे-से-सामने घुमाने से उसका आकार नहीं बदलता है, इसलिए तीन टिकटों में केवल दो तह होते हैं, एक एस-वक्र और एक सर्पिल। अधिक सामान्य रूप से, इस परिभाषा के साथ तहों की संख्या 1,1,2,5,14,38,120,353,1148,3527,11622,36627,121622,389560,1301140,4215748 हैं। मानचित्र तह यह सवाल है कि एक आयताकार मानचित्र को उसके क्रीज़ के साथ मोड़ने के कितने तरीके हैं, जिससे प्रत्येक क्रीज़ को पहाड़ या घाटी मोड़ बनाने की अनुमति मिलती है। यह स्टाम्प फोल्डिंग से अलग है क्योंकि इसमें केवल एक दिशा में क्रीज़ के बजाय ऊर्ध्वाधर और क्षैतिज दोनों क्रीज़ शामिल हैं। मानचित्र को मोड़ने के एक अलग तरीके के रूप में मुड़े हुए वर्गों के प्रत्येक अलग-अलग ऊर्ध्वाधर अनुक्रम को गिनते हुए, इसकी क्रीज़ के साथ 2×2 मानचित्र को मोड़ने के आठ तरीके हैंः हालाँकि, मानचित्र को मोड़ने के तरीकों की संख्या की गिनती की सामान्य समस्या अनसुलझी रहती है। मानचित्र को मोड़ने के तरीकों की संख्या केवल इसके लिए जानी जाती है। वे हैंः 1,8,1368,300608,186086600,123912532224,129950723279272। जटिलता मानचित्र के तह और मुहर के तह की समस्याएं ओरिगामी के गणित में एक समस्या से संबंधित हैं कि क्या क्रीज पैटर्न वाले वर्ग को एक सपाट आकृति में मोड़ दिया जा सकता है। यदि डाक टिकटों की एक पट्टी के प्रत्येक क्रीज को एक मोड़ने की दिशा (या तो एक पहाड़ी मोड़ या एक घाटी मोड़) दी जाती है, तो यह परीक्षण करना संभव है कि क्या परिणाम को बहुपद समय में सपाट मोड़ दिया जा सकता है। मानचित्र पर एक ही समस्या के लिए (निर्दिष्ट दिशाओं के साथ क्रीज़ द्वारा आयतों में विभाजित) यह अज्ञात है कि क्या एक बहुपद समय तह एल्गोरिथ्म सामान्य रूप से मौजूद है, हालांकि एक बहुपद एल्गोरिथ्म मानचित्रों के लिए जाना जाता है। एक प्रतिबंधित मामले में जहां मानचित्र को "सरल" तहों के अनुक्रम से मोड़ना होता है, जो कागज को एक ही रेखा के साथ मोड़ते हैं, समस्या बहुपद होती है। समस्या के कुछ विस्तार, उदाहरण के लिए कागज के गैर-आयताकार पत्रकों के लिए, एनपी-पूर्ण हैं। यहां तक कि डाक टिकटों की एक-आयामी पट्टी के लिए, जिसमें पहले से ही पहाड़ या घाटी के मोड़ के रूप में लेबल की गई क्रीज़ हैं, इसे मोड़ने का एक तरीका खोजना एन. पी.-कठिन है जो किसी भी क्रीज़ के दो डाक टिकटों के बीच स्थित डाक टिकटों की अधिकतम संख्या को कम करता है। नियमित पेपर फोल्डिंग अनुक्रम भी देखें, जो 0s और 1s का एक अनंत अनुक्रम है जो डाक टिकटों की पट्टियों को मोड़ने के एक तरीके का वर्णन करता है संदर्भ बाहरी लिंक "लेबल किए गए डाक टिकटों की एक पट्टी को मोड़ना" द वोल्फ्राम डेमॉन्स्ट्रेशन प्रोजेक्ट सेः http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps पेपर फोल्डिंग गणित में अनसुलझी समस्याएं