التبديل الفائق

الموسوعة الحرة
توزيع التباديل في تبديل فائق مكون من 3 رموز

في الرياضيات التوافقية ، يُعرف التبديل الفائق على n رمزًا بأنه سلسلة تحتوي على كل تبديل من n رمزًا كسلسلة فرعية . بينما يمكن تكوين التبديلات الفائقة البسيطة من جميع التبديلات المتصلة ببعضها، يمكن أن تكون التبديلات الفائقة أقصر (باستثناء الحالة البسيطة n = 1) نظرًا لإمكانية التداخل. على سبيل المثال، في حالة n = 2، يحتوي التبديل الفائق 1221 على جميع التبديلات الممكنة (12 و21)، ولكن السلسلة الأقصر 121 تحتوي أيضًا على كلا التبديلين.

لقد ثبت أنه بالنسبة لـ 1 ≤ n ≤ 5، فإن أصغر تبديل فائق على n رمزًا يكون طوله 1! + 2! + … + n ! (المتتالية A180632 في OEIS ) . [ 1 ] أصغر أربعة تبديلات فائقة لها أطوال 1، 3، 9، و33 على التوالي، مُشكلةً السلاسل 1، 121، 123121321، و123412314231243121342132413214321. مع ذلك، بالنسبة لـ n = 5، توجد عدة تبديلات فائقة صغيرة طولها 153. أحد هذه التبديلات الفائقة مُوضح أدناه، بينما يُمكن الحصول على تبديل آخر بنفس الطول عن طريق تبديل جميع الأرقام 4 و5 في النصف الثاني من السلسلة (بعد الرقم 2 المكتوب بخط غامق ): [ 2 ]

12345123 4152341253412354 1231452314253142 35142315 42312453 1243512431524312 5431 2 134 52134251 34215342 13542132 4513241532413524 1325413214532143 52143251 432154321

بالنسبة لحالات n > 5، لم يتم إثبات أصغر تبديل فائق بعد، ولا تم إيجاد نمط لإيجادها، ولكن تم العثور على حدود دنيا وعليا لها.

إيجاد التباديل الفائقة

رسم تخطيطي لإنشاء تبديل فائق مكون من 3 رموز من تبديل فائق مكون من رمزين

إحدى أكثر الخوارزميات شيوعًا لإنشاء تبديل فائق من الرتبةن{\displaystyle n}هي خوارزمية تكرارية. أولاً، التبديل الفائق من الرتبةن-1{\displaystyle n-1}يُقسّم إلى تباديله الفردية بالترتيب الذي ظهرت به في التبديل الفائق. ثم يُوضع كل تبديل من هذه التبديلات بجوار نسخة منه مع إضافة رمز رقم n بين النسختين. وأخيرًا، تُوضع كل بنية ناتجة بجوار الأخرى، وتُدمج جميع الرموز المتطابقة المتجاورة. [ 3 ]

على سبيل المثال، يمكن إنشاء تبديل فائق من الرتبة 3 من تبديل يحتوي على رمزين؛ بدءًا من التبديل الفائق 121 وتقسيمه إلى التبديلين 12 و21، ثم نسخ التبديلين ووضعهما معًا ليصبحا 12312 و21321. يتم وضعهما معًا لإنشاء 1231221321، ويتم دمج الرقمين 2 المتجاورين المتطابقين في المنتصف لإنشاء 123121321، وهو بالفعل تبديل فائق من الرتبة 3. ينتج عن هذه الخوارزمية أقصر تبديل فائق ممكن لجميع قيم n الأقل من أو تساوي 5، ولكنه يصبح أطول من أقصر تبديل ممكن كلما زادت قيمة n عن ذلك. [ 3 ]

تتمثل إحدى طرق إيجاد التباديل الفائقة في إنشاء رسم بياني حيث يمثل كل تبديل رأسًا ، وترتبط جميع التبديلات بحافة. ​​لكل حافة وزن مرتبط بها؛ يُحسب الوزن بمعرفة عدد الأحرف التي يمكن إضافتها إلى نهاية أحد التبديلات (مع حذف نفس العدد من الأحرف من البداية) للحصول على التبديل الآخر. [ 3 ] على سبيل المثال، الحافة من 123 إلى 312 وزنها 2 لأن 123 + 12 = 12312 = 312. أي مسار هاميلتوني عبر الرسم البياني المُنشأ هو تبديل فائق، وتصبح مشكلة إيجاد المسار ذي الوزن الأصغر شكلًا من أشكال مسألة البائع المتجول . أول مثال لتبديل فائق أصغر من طول1!+2!+...+ن!{\displaystyle 1!+2!+\ldots +n!}تم التوصل إلى هذه النتيجة باستخدام بحث حاسوبي حول هذه الطريقة بواسطة روبن هيوستن.

الحدود الدنيا، أو مشكلة هاروهي

في سبتمبر 2011، أثبت مستخدم مجهول على لوحة العلوم والرياضيات ( /sci/ ) في موقع 4chan أن أصغر تبديل فائق على n رمزًا ( حيث n ≥ 2) لا يقل طوله عن n ! + ( n − 1)! + ( n − 2)! + n − 3. [ 4 ] وبالإشارة إلى مسلسل الأنمي الياباني "كآبة هاروهي سوزوميا " ، وتحديدًا حقيقة أنه عُرض في الأصل كسرد غير خطي ، طُرحت المسألة على لوحة الصور تحت عنوان "مسألة هاروهي": [ 5 ] إذا أردت مشاهدة حلقات الموسم الأول الأربعة عشر من المسلسل بكل ترتيب ممكن، فما هي أقصر سلسلة من الحلقات التي ستحتاج إلى مشاهدتها؟ [ 6 ] حظي برهان هذا الحد الأدنى باهتمام الجمهور في أكتوبر 2018، بعد أن غردت عالمة الرياضيات وعلوم الحاسوب روبن هيوستن عنه. [ 4 ] في 25 أكتوبر 2018، نشر كلٌّ من روبن هيوستن وجاي بانتون وفينس فاتر نسخةً مُنقّحةً من هذا البرهان في الموسوعة الإلكترونية لتسلسلات الأعداد الصحيحة (OEIS)، ونُسب الفضل في ذلك إلى "ناشر مجهول على موقع 4chan". [ 6 ] [ 1 ]

بالنسبة لمسألة "هاروهي" تحديدًا (حالة 14 رمزًا)، يبلغ الحد الأدنى والحد الأقصى الحاليان 93,884,313,611 و93,924,230,411 على التوالي. [ 4 ] وهذا يعني أن مشاهدة المسلسل بكل ترتيب ممكن ستتطلب حوالي 4.3 مليون سنة. [ 7 ]

الحدود العليا

في 20 أكتوبر 2018، قام الكاتب والرياضي غريغ إيغان، بتكييف بناءٍ وضعه آرون ويليامز لإنشاء مسارات هاميلتونية عبر مخطط كايلي للمجموعة المتناظرة ، [ 8 ] فابتكر خوارزميةً لإنتاج تباديل فائقة بطول n ! + ( n -1)! + ( n -2)! + ( n -3)! + n -3. [ 3 ] وحتى عام 2018، كانت هذه أصغر التباديل الفائقة المعروفة لـ n ≥ 7. ومع ذلك، في 1 فبراير 2019، أعلن بوغدان كواندا أنه وجد تبديلاً فائقاً لـ n=7 بطول 5907، أو ( n ! + ( n -1)! + ( n -2)! + ( n - 3)! + n -3)-1، وهو رقم قياسي جديد. [ 3 ] في 27 فبراير 2019، وباستخدام أفكار طورها روبن هيوستن، ابتكر إيغان تبديلاً فائقاً لـ n = 7 بطول 5906. [ 3 ] يبقى السؤال مطروحاً حول ما إذا كانت هناك تبديلات فائقة أقصر مماثلة لقيم n > 7. ولا يزال الحد الأدنى الأفضل الحالي (انظر القسم أعلاه) لـ n = 7 هو 5884.

انظر أيضاً

للمزيد من القراءة

مراجع

  1. ١ ٢ ناشر مجهول على موقع 4chan؛ هيوستن، روبن؛ بانتون، جاي؛ فاتر، فينس (٢٥ أكتوبر ٢٠١٨). "الحد الأدنى لطول أقصر نمط فائق" (ملف PDF) . OEIS . تم الاطلاع عليه بتاريخ ٢٧ أكتوبر ٢٠١٨ .
  2. ↑ جونستون، ناثانيال (28 يوليو 2013). "عدم تفرد التبديلات الفائقة الدنيا" . الرياضيات المتقطعة . 313 (14): 1553-1557 . arXiv : 1303.4150 . Bibcode : 2013arXiv1303.4150J . doi : 10.1016/j.disc.2013.03.024 . S2CID 12018639. Zbl 1368.05004 . تاريخ الاسترجاع: 16 مارس 2014 .  
  3. 1 2 3 4 5 6 إيغان، غريغ (20 أكتوبر 2018). "التباديل الفائقة" . gregegan.net . تم الاطلاع عليه في 15 يناير 2020 .
  4. 1 2 3 غريغز، ماري بيث (24 أكتوبر 2018). "منشور مجهول على موقع 4chan قد يساعد في حل لغز رياضي عمره 25 عامًا" . ذا فيرج .
  5. ↑ مجهول (17 سبتمبر 2011). "سلسلة التباديل III" . واروسو .
  6. 1 2 كلاريش، إريكا (5 نوفمبر 2018). "كاتب الخيال العلمي جريج إيجان وعبقري رياضيات مجهول يطوران مسألة التبديل" . مجلة كوانتا . تم الاطلاع عليه في 21 يونيو 2020 .
  7. ↑ سبالدينغ، كاتي (30 أكتوبر 2018). "موقع 4chan يحل لغزًا رياضيًا عمره عقود" . IFLScience . تم الاطلاع عليه بتاريخ 5 أكتوبر 2023 .
  8. ↑ آرون، ويليامز (2013). "هاميلتونية الرسم البياني الموجه لكايلي على المجموعة المتناظرة المولدة بواسطة σ = (1 2 ... n) و τ = (1 2)". arXiv : 1307.2549v3 [ math.CO ].