طي الخرائط

في رياضيات طي الورق ، يُعدّ طي الخرائط وطي الطوابع مسألتين لحساب عدد الطرق الممكنة لطي ورقة. في مسألة طي الطوابع، تكون الورقة عبارة عن شريط من الطوابع بينها طيات، ويجب أن تقع الطيات على هذه الطيات. أما في مسألة طي الخرائط، فتكون الورقة عبارة عن خريطة مقسمة إلى مستطيلات بواسطة الطيات، ويجب أن تقع الطيات أيضًا على طول هذه الطيات فقط.

ينسب لوكاس (1891) اختراع مسألة طي الطوابع إلى إميل ليموين . ^{[ 1 ]} ويقدم توشارد (1950) العديد من المراجع المبكرة الأخرى. ^{[ 2 ]}

في مسألة طي الطوابع، تكون الورقة المراد طيها عبارة عن شريط من الطوابع المربعة أو المستطيلة، مفصولة بخطوط طي، ولا يمكن طي الطوابع إلا على طول هذه الخطوط. في إحدى الصيغ الشائعة لهذه المسألة، يُعتبر كل طابع مميزًا عن غيره، لذا يُعتبر طي شريط من الطوابع متكافئًا فقط عندما يكون ترتيب الطوابع فيه رأسيًا كما هو. ^{[ 3 ]} على سبيل المثال، هناك ست طرق لطي شريط من ثلاثة طوابع مختلفة:

تشمل هذه جميع التباديل الستة للطوابع، ولكن بالنسبة لأكثر من ثلاثة طوابع، لا تكون جميع التباديل ممكنة. إذا كان هناك، بالنسبة لتبديل p ، عددان i و j لهما نفس الزوجية بحيث تظهر الأعداد الأربعة i و j و i + 1 و j + 1 في p بهذا الترتيب الدوري ، فلا يمكن طي p . يقتضي شرط الزوجية أن تظهر الطيات بين الطابعين i و i + 1 ، وبين الطابعين j و j + 1 ، على نفس جانب كومة الطوابع المطوية، لكن شرط الترتيب الدوري يقتضي أن تتقاطع هاتان الطيتان، وهو أمر مستحيل فيزيائيًا. على سبيل المثال، لا يمكن طي التبديل المكون من أربعة عناصر 1324، لأنه يحتوي على هذا النمط المحظور مع i = 1 و j = 3. يمكن طي جميع التباديل المتبقية، التي لا تحتوي على هذا النمط. ^{[ 3 ]} يُعطى عدد الطرق المختلفة لطي شريط من n طابعًا بالمتتالية

1، 2، 6، 16، 50، 144، 462، 1392، 4536، 14060، 46310، 146376، 485914، 1557892، 5202690، ... (التسلسل A000136 في OEIS ) .

هذه الأعداد قابلة للقسمة دائمًا على n (لأن التبديل الدوري لتسلسل طوابع قابلة للطي يكون دائمًا قابلًا للطي)، ^{[ 3 ] [ 4 ]} وناتج هذه القسمة هو

1، 1، 2، 4، 10، 24، 66، 174، 504، 1406، 4210، 12198، 37378، 111278، 346846، 1053874، ... ( التسلسل A000682 في OEIS )

عدد الطرق المتميزة طوبولوجيًا التي يمكن لمنحنى نصف لانهائي أن يتقاطع بها مع خط ما n مرة، وتُسمى هذه الطرق "أنصاف التعرجات". وهي ترتبط ارتباطًا وثيقًا بالتعرجات ، وهي الطرق التي يمكن لمنحنى مغلق أن يتقاطع بها مع خط ما بنفس العدد من المرات. تُقابل التعرجات حلول مسألة طي الطوابع، حيث يمكن توصيل الطابع الأول والأخير معًا لتشكيل حلقة متصلة من الطوابع.

في ستينيات القرن العشرين، قام جون إي. كوهلر و دبليو إف لونون بتطوير خوارزميات مكّنت آنذاك من حساب هذه الأرقام لما يصل إلى 28 طابعًا بريديًا. ^{[ 5 ] [ 6 ] [ 7 ]} وعلى الرغم من الأبحاث الإضافية، فإن الطرق المعروفة لحساب هذه الأرقام تستغرق وقتًا أُسّيًا كدالة لـ n . ^{[ 8 ] [ 9 ]} وبالتالي، لا توجد صيغة أو خوارزمية فعّالة معروفة يمكنها توسيع هذه المتتالية لتشمل قيمًا كبيرة جدًا لـ n . ومع ذلك، يمكن استخدام أساليب استدلالية من الفيزياء للتنبؤ بمعدل النمو الأُسّي لهذه المتتالية. ^{[ 10 ]}

عادةً ما تُركز مسألة طي الطوابع على عدد حالات الطي الممكنة لشريط الطوابع فقط، دون النظر إلى إمكانية إنشاء الطية فعليًا من خلال سلسلة من الحركات تبدأ من شريط طوابع غير مطوي. مع ذلك، ووفقًا لحل مسألة قاعدة النجار ، يمكن إنشاء كل حالة طي (أو بعبارة أخرى، يمكن فردها). ^{[ 11 ]}

في صيغة أخرى لمسألة طي الطوابع، تُعتبر مجموعة الطوابع فارغة، بحيث لا يمكن تمييز أحد طرفيها عن الآخر، ويُعتبر طيان منفصلين فقط عندما يكون لهما شكلان مختلفان. ولا يُعتبر قلب الشريط المطوي رأسًا على عقب أو من الخلف إلى الأمام تغييرًا في شكله، لذا فإن ثلاثة طوابع لها طيتان فقط، منحنى على شكل حرف S وحلزوني. ^{[ 3 ]} وبشكل عام، فإن عدد الطيات وفقًا لهذا التعريف هو

1، 1، 2، 5، 14، 38، 120، 353، 1148، 3527، 11622، 36627، 121622، 389560، 1301140، 4215748، ... (التسلسل A001011 في OEIS )

طي الخرائط هو مسألة تحديد عدد الطرق الممكنة لطي خريطة مستطيلة على طول طياتها، بحيث يشكل كل طية إما طية جبلية أو طية وادي. ويختلف عن طي الطوابع في أنه يشمل طيات رأسية وأفقية، بدلاً من الطيات في اتجاه واحد فقط. ^{[ 12 ]}

هناك ثماني طرق لطي خريطة 2 × 2 على طول طياتها، مع احتساب كل تسلسل رأسي مختلف من المربعات المطوية كطريقة مميزة لطي الخريطة: ^{[ 5 ]}

مع ذلك، لا تزال المشكلة العامة المتمثلة في حساب عدد طرق طي خريطة ما دون حل. ولا يُعرف عدد طرق طي خريطة من الرتبة n × n إلا عندما تكون n ≤ 7. وهي كالتالي:

1، 8، 1368، 300608، 186086600، 123912532224، 129950723279272 (التسلسل A001418 في OEIS ) .

ترتبط مشكلتا طي الخرائط وطي الطوابع بمسألة في رياضيات الأوريغامي، وهي إمكانية طي مربع ذي نمط طيات ليصبح شكلاً مسطحاً. إذا تم تحديد اتجاه طي (إما طي جبلي أو طي وادي ) لكل طية من طيات شريط الطوابع، فمن الممكن اختبار إمكانية طي الشكل الناتج ليصبح مسطحاً في زمن متعدد الحدود . ^{[ 13 ]}

بالنسبة للمسألة نفسها على خريطة (مقسمة إلى مستطيلات بواسطة طيات ذات اتجاهات محددة)، فإنه من غير المعروف ما إذا كانت هناك خوارزمية طي ذات زمن متعدد الحدود بشكل عام، على الرغم من وجود خوارزمية متعددة الحدود معروفة للخرائط من الرتبة 2 × n . ^{[ 14 ]} في حالة محدودة حيث يتم طي الخريطة بسلسلة من الطيات "البسيطة" التي تطوي الورقة على طول خط واحد، تكون المسألة متعددة الحدود. بعض امتدادات المسألة، على سبيل المثال إلى أوراق غير مستطيلة، هي مسائل NP-كاملة . ^{[ 13 ]}

حتى بالنسبة لشريط طوابع أحادي البعد، مع وجود طياته المصنفة مسبقًا على أنها طيات جبلية أو طيات وادي، فإن إيجاد طريقة لطيّه بحيث تقلل من الحد الأقصى لعدد الطوابع التي تقع بين طابعين في أي طية يُعدّ مسألة صعبة من نوع NP . ^{[ 15 ]}

• تسلسل طي الورق المنتظم ، وهو تسلسل لانهائي من الأصفار والآحاد يصف إحدى طرق طي شرائط الطوابع.

• وايسشتاين، إريك دبليو ، " طي الخرائط " (" طي الطوابع ") في عالم الرياضيات .
• "طي شريط من الطوابع المُلصقة" من مشروع عروض وولفرام التوضيحية: http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps/