Map folding
کاغذی فولڈنگ کی ریاضی میں، نقشہ فولڈنگ اور اسٹیمپ فولڈنگ ان طریقوں کی گنتی کے دو مسائل ہیں جن سے کاغذ کے ٹکڑے کو فولڈ کیا جا سکتا ہے۔ ڈاک ٹکٹ کے فولڈنگ کے مسئلے میں، کاغذ ڈاک ٹکٹوں کی ایک پٹی ہوتی ہے جس کے درمیان کریز ہوتے ہیں، اور فولڈز کو کریز پر ہونا چاہیے۔ نقشے کے فولڈنگ کے مسئلے میں، کاغذ ایک نقشہ ہوتا ہے، جسے کریز کے ذریعے آئتاکار میں تقسیم کیا جاتا ہے، اور فولڈز کو دوبارہ صرف ان کریز کے ساتھ ہی ہونا چاہیے۔ اسٹامپ فولڈنگ کے مسئلے کی ایجاد کا سہرا ایمیل لیموائن کو جاتا ہے۔ کئی دیگر ابتدائی حوالہ جات فراہم کرتا ہے۔ لیبل والے ڈاک ٹکٹ ڈاک ٹکٹ کے فولڈنگ کے مسئلے میں، جوڑنے کے لیے کاغذ مربع یا آئتاکار ڈاک ٹکٹوں کی ایک پٹی ہوتی ہے، جسے کریز سے الگ کیا جاتا ہے، اور ڈاک ٹکٹوں کو صرف ان کریز کے ساتھ جوڑ دیا جا سکتا ہے۔ مسئلہ کے ایک عام طور پر سمجھے جانے والے ورژن میں، ہر ڈاک ٹکٹ کو ایک دوسرے کے ڈاک ٹکٹ سے ممتاز سمجھا جاتا ہے، لہذا ڈاک ٹکٹوں کی ایک پٹی کے دو فولڈنگ کو صرف اس صورت میں مساوی سمجھا جاتا ہے جب ان میں ڈاک ٹکٹوں کی ایک ہی عمودی ترتیب ہو۔ مثال کے طور پر، تین مختلف ڈاک ٹکٹوں کی ایک پٹی کو جوڑنے کے چھ طریقے ہیں: ان میں ڈاک ٹکٹوں کی تمام چھ تغیرات شامل ہیں، لیکن تین سے زیادہ ڈاک ٹکٹوں کے لیے تمام تغیرات ممکن نہیں ہیں۔ اگر، کسی ترتیب کے لیے، دو اعداد ہیں اور ایک ہی برابری کے ساتھ اس طرح کہ چار اعداد،،، اور اس چکور ترتیب میں ظاہر ہوتے ہیں، تو جوڑ نہیں کیا جا سکتا۔ برابری کی شرط سے یہ ظاہر ہوتا ہے کہ ڈاک ٹکٹوں اور ڈاک ٹکٹوں کے درمیان اور ڈاک ٹکٹوں اور ڈاک ٹکٹوں کے درمیان کریز فولڈڈ ڈاک ٹکٹوں کے اسٹیک کے ایک ہی طرف ظاہر ہوتے ہیں، لیکن چکور ترتیب کی حالت سے یہ ظاہر ہوتا ہے کہ یہ دونوں کریز ایک دوسرے کو عبور کرتے ہیں، جو کہ ایک جسمانی ناممکن ہے۔ مثال کے طور پر، چار عنصر کی ترتیب 1324 کو جوڑ نہیں کیا جا سکتا، کیونکہ اس میں اور کے ساتھ یہ ممنوع نمونہ ہے۔ اس نمونے کے بغیر باقی تمام تغیرات کو جوڑ دیا جا سکتا ہے۔ ڈاک ٹکٹوں کی پٹی کو جوڑنے کے مختلف طریقوں کی تعداد ترتیب 1، 2، 6، 16، 50، 144، 462، 1392، 4536، 14060، 46310، 1466376، 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، 11122، 36627، 121622، 389560، 1301140، 4215748 ہیں۔ نقشہ نقشہ فولڈنگ یہ سوال ہے کہ ایک آئتاکار نقشے کو اس کی کریز کے ساتھ جوڑنے کے کتنے طریقے ہیں، جس سے ہر کریز کو پہاڑ یا وادی فولڈ بنانے کی اجازت ملتی ہے۔ یہ اسٹامپ فولڈنگ سے اس لحاظ سے مختلف ہے کہ اس میں عمودی اور افقی دونوں کریز شامل ہیں، بجائے اس کے کہ صرف ایک ہی سمت میں کریز ہوں۔ نقشے کو جوڑنے کے ایک الگ طریقے کے طور پر، جوڑے ہوئے مربعوں کی ہر مختلف عمودی ترتیب کو گنتے ہوئے، 2×2 نقشے کو اس کی کریز کے ساتھ جوڑنے کے آٹھ طریقے ہیں: تاہم، نقشے کو جوڑنے کے طریقوں کی تعداد گننے کا عمومی مسئلہ حل نہیں ہوا ہے۔ نقشے کو جوڑنے کے طریقوں کی تعداد صرف اس کے لیے معلوم ہوتی ہے۔ وہ ہیں: 1، 8، 1368، 300608، 186086600، 123912532224، 129950723279272۔ پیچیدگی نقشہ فولڈنگ اور اسٹیمپ فولڈنگ کے مسائل اوریگامی کی ریاضی میں ایک مسئلے سے متعلق ہیں کہ آیا کریز پیٹرن والے مربع کو فلیٹ شکل میں جوڑ دیا جا سکتا ہے۔ اگر ڈاک ٹکٹوں کی ایک پٹی کے ہر کریز کو فولڈنگ کی سمت (یا تو ایک پہاڑی فولڈ یا وادی فولڈ) تفویض کی جاتی ہے، تو یہ جانچنا ممکن ہے کہ آیا نتیجہ کثیر الجہتی وقت میں فلیٹ کیا جا سکتا ہے۔ نقشے پر اسی مسئلے کے لیے (مقررہ سمتوں کے ساتھ کریز کے ذریعے مستطیلوں میں تقسیم) یہ معلوم نہیں ہے کہ آیا عام طور پر کثیر الجہتی ٹائم فولڈنگ الگورتھم موجود ہے، حالانکہ کثیر الجہتی الگورتھم نقشوں کے لیے جانا جاتا ہے۔ ایک محدود صورت میں جہاں نقشے کو "سادہ" فولڈز کی ترتیب سے جوڑنا ہوتا ہے، جو کاغذ کو ایک ہی لائن کے ساتھ جوڑتا ہے، مسئلہ کثیر الجہتی ہوتا ہے۔ مسئلہ کی کچھ توسیعات، مثال کے طور پر کاغذ کی غیر مستطیل چادروں تک، این پی مکمل ہیں۔ یہاں تک کہ ڈاک ٹکٹوں کی ایک جہتی پٹی کے لیے، جس کی کریز پر پہلے سے ہی پہاڑ یا وادی کے فولڈ کے طور پر لیبل لگا ہوا ہے، اسے جوڑنے کا ایسا طریقہ تلاش کرنا این پی مشکل ہے جو کسی بھی کریز کے دو ڈاک ٹکٹوں کے درمیان زیادہ سے زیادہ ڈاک ٹکٹوں کی تعداد کو کم سے کم کرے۔ باقاعدہ پیپر فولڈنگ کا تسلسل بھی دیکھیں، 0s اور 1s کا ایک لامحدود تسلسل جو ڈاک ٹکٹوں کی فولڈنگ سٹرپس کا ایک طریقہ بیان کرتا ہے حوالہ جات بیرونی لنکس "فولڈنگ اے سٹرپ آف لیبلڈ اسٹیمپس" سے وولفرم ڈیمنسٹریشن پروجیکٹ: http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps کاغذ فولڈنگ ریاضی میں حل نہ ہونے والے مسائل