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। জটিলতা মানচিত্র ভাঁজ এবং স্ট্যাম্প ভাঁজ সমস্যাগুলি অরিগামির গণিতে একটি সমস্যার সাথে সম্পর্কিত যে একটি ক্রিজ প্যাটার্ন সহ একটি বর্গক্ষেত্রকে একটি সমতল আকৃতিতে ভাঁজ করা যেতে পারে কিনা। যদি একটি ভাঁজ দিক (হয় একটি পাহাড়ের ভাঁজ বা একটি উপত্যকার ভাঁজ) স্ট্যাম্পের প্রতিটি খাঁজকে বরাদ্দ করা হয়, তবে ফলাফলটি বহুপদী সময়ে সমতল ভাঁজ করা যেতে পারে কিনা তা পরীক্ষা করা সম্ভব। একটি মানচিত্রে একই সমস্যার জন্য (নির্দিষ্ট দিকনির্দেশনা সহ ক্রিজ দ্বারা আয়তক্ষেত্রে বিভক্ত) এটি অজানা যে একটি বহুপদী সময় ভাঁজ অ্যালগরিদম সাধারণভাবে বিদ্যমান কিনা, যদিও একটি বহুপদী অ্যালগরিদম মানচিত্রের জন্য পরিচিত। একটি সীমাবদ্ধ ক্ষেত্রে যেখানে মানচিত্রটি "সাধারণ" ভাঁজগুলির একটি ক্রম দ্বারা ভাঁজ করতে হবে, যা একটি একক লাইন বরাবর কাগজটি ভাঁজ করে, সমস্যাটি বহুপদী। সমস্যার কিছু সম্প্রসারণ, উদাহরণস্বরূপ কাগজের অ-আয়তক্ষেত্রাকার শীটে, এনপি-সম্পূর্ণ। এমনকি এক-মাত্রিক স্ট্যাম্পের জন্য, যার ক্রিজগুলি ইতিমধ্যে পর্বত বা উপত্যকার ভাঁজ হিসাবে লেবেলযুক্ত, এটি ভাঁজ করার এমন একটি উপায় খুঁজে পাওয়া এনপি-কঠিন যা কোনও ক্রিজের দুটি স্ট্যাম্পের মধ্যে থাকা স্ট্যাম্পের সর্বাধিক সংখ্যাকে কমিয়ে দেয়। আরও দেখুন নিয়মিত কাগজ ভাঁজ করার ক্রম, 0 এবং 1-এর একটি অসীম ক্রম যা ডাকটিকিটের ভাঁজ করার স্ট্রিপগুলির একটি উপায় বর্ণনা করে রেফারেন্স বাহ্যিক লিঙ্কগুলি "লেবেলযুক্ত স্ট্যাম্পগুলির একটি স্ট্রিপ ভাঁজ করা" দ্য ওল্ফ্রাম ডেমন্সট্রেশন প্রজেক্ট থেকেঃ http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps কাগজের ভাঁজ গণিতের অমীমাংসিত সমস্যা