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,36622,389560,1301140,4215748, ஆகும். வரைபட வரைபட மடிப்பு என்பது ஒரு செவ்வக வரைபடத்தை அதன் மடிப்புகளுடன் மடிப்பதற்கு எத்தனை வழிகள் உள்ளன என்ற கேள்வி, ஒவ்வொரு க்ரீஸையும் ஒரு மலை அல்லது பள்ளத்தாக்கு மடிப்பை உருவாக்க அனுமதிக்கிறது. இது முத்திரை மடிப்புகளிலிருந்து வேறுபடுகிறது, இது ஒரு திசையில் மட்டுமே மடிப்புகளைக் காட்டிலும் செங்குத்து மற்றும் கிடைமட்ட மடிப்புகளை உள்ளடக்கியது. ஒரு 2x2 வரைபடத்தை அதன் மடிப்புகளுடன் மடிப்பதற்கு எட்டு வழிகள் உள்ளன, மடிக்கப்பட்ட சதுரங்களின் ஒவ்வொரு வெவ்வேறு செங்குத்து வரிசையையும் வரைபடத்தை மடிப்பதற்கான ஒரு தனித்துவமான வழியாக எண்ணும்ஃ இருப்பினும், ஒரு வரைபடத்தை மடிப்பதற்கான வழிகளின் எண்ணிக்கையை எண்ணும் பொதுவான சிக்கல் தீர்க்கப்படாமல் உள்ளது. ஒரு வரைபடத்தை மடிப்பதற்கான வழிகளின் எண்ணிக்கை மட்டுமே அறியப்படுகிறது. அவை இவைஃ 1,8,1368,300608,186086600,123912532224,129950723279272. சிக்கலானது வரைபட மடிப்பு மற்றும் முத்திரை மடிப்பு சிக்கல்கள் ஓரிகமியின் கணிதத்தில் ஒரு க்ரீஸ் வடிவம் கொண்ட ஒரு சதுரத்தை ஒரு தட்டையான உருவத்துடன் மடிக்க முடியுமா என்ற சிக்கலுடன் தொடர்புடையவை. ஒரு மடிப்பு திசை (ஒரு மலை மடிப்பு அல்லது ஒரு பள்ளத்தாக்கு மடிப்பு) முத்திரைகளின் ஒவ்வொரு மடிப்புக்கும் ஒதுக்கப்பட்டால், முடிவை பல்லுறுப்புக்கோவை நேரத்தில் தட்டையாக மடிக்க முடியுமா என்பதை சோதிக்க முடியும். ஒரு வரைபடத்தில் உள்ள அதே சிக்கலுக்கு (ஒதுக்கப்பட்ட திசைகளுடன் மடிப்புகளால் செவ்வகங்களாகப் பிரிக்கப்பட்டுள்ளது) ஒரு பல்லுறுப்புக்கோவை நேர மடிப்பு வழிமுறை பொதுவாக இருக்கிறதா என்பது தெரியவில்லை, இருப்பினும் ஒரு பல்லுறுப்புக்கோவை வழிமுறை வரைபடங்களுக்கு அறியப்படுகிறது. ஒரு வரையறுக்கப்பட்ட வழக்கில், வரைபடத்தை "எளிய" மடிப்புகளின் வரிசையால் மடிக்க வேண்டும், இது காகிதத்தை ஒரே வரியில் மடிக்கிறது, சிக்கல் பல்லுறுப்புக்கோவை ஆகும். சிக்கலின் சில நீட்டிப்புகள், எடுத்துக்காட்டாக செவ்வகமற்ற காகிதத் தாள்களுக்கு, NP-முழுமையானவை. மலை அல்லது பள்ளத்தாக்கு மடிப்புகள் என்று ஏற்கனவே முத்திரை குத்தப்பட்ட ஒரு பரிமாண முத்திரைக்கு கூட, எந்தவொரு மடிப்பின் இரண்டு முத்திரைகளுக்கு இடையில் இருக்கும் அதிகபட்ச முத்திரைகளின் எண்ணிக்கையைக் குறைக்கும் ஒரு வழியைக் கண்டுபிடிப்பது NP-கடினம். வழக்கமான காகித மடிப்பு வரிசையையும் பார்க்கவும், முத்திரைகளின் மடிப்பு துண்டுகளின் ஒரு வழியை விவரிக்கும் 0s மற்றும் 1s இன் எல்லையற்ற வரிசை குறிப்புகள் வெளிப்புற இணைப்புகள் "லேபிள் செய்யப்பட்ட முத்திரைகளின் ஒரு துண்டு மடிப்பு" தி வொல்ப்ராம் ஆர்ப்பாட்டங்கள் திட்டத்திலிருந்துஃ http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps காகித மடிப்பு கணிதத்தில் தீர்க்கப்படாத சிக்கல்கள்