عن برج هانوي | القواعد و2ⁿ−1 والأسطورة

ثلاثة أوتاد ومخروط من الأقراص

تحتوي اللوحة على ثلاثة أوتاد. الأقراص كلها مختلفة الأحجام وتُدخَل في الأوتاد. في البداية تكون المجموعة كلها على وتد واحد، مرتبة حسب الحجم، أكبرها في الأسفل وأصغرها في الأعلى، فتأخذ الكومة شكل مخروط. الهدف هو نقل هذا البرج كله إلى وتد آخر.

لغز برج هانوي خشبي بأقراص مكدسة على ثلاثة أوتاد — لغز برج هانوي الخشبي. صورة: PranavAmbhore، CC BY-SA 3.0

القواعد الثلاث

1. انقل قرصًا واحدًا فقط في كل مرة. 2. النقلة تأخذ القرص العلوي من كومة وتضعه على كومة أخرى أو على وتد فارغ. 3. لا يجوز أبدًا أن يستقر قرص أكبر فوق قرص أصغر. هذه القواعد الثلاث هي اللعبة كلها. وبها يكون كل موضع مسموح به طريقةً لتوزيع الأقراص على الأوتاد مع بقاء كل وتد مرتبًا.

أقصر حل هو 2ⁿ − 1

أقل عدد من النقلات يحل برجًا من n من الأقراص هو 2ⁿ − 1. القرص الواحد يحتاج إلى نقلة واحدة. والقرصان إلى 3. والثلاثة إلى 7، والأربعة إلى 15، والخمسة إلى 31. كل قرص جديد يضاعف الحل السابق ويضيف النقلة الواحدة التي تحمل القرص الأكبر: إذا احتاجت n − 1 من الأقراص إلى T نقلة، فإن n من الأقراص تحتاج إلى 2T + 1. وهذه العلاقة التكرارية تساوي 2ⁿ − 1 تمامًا. ثمانية أقراص، وهو أعلى برج في تطبيق PictorX، تحتاج إلى 255 نقلة. لا يوجد مسار مسموح به أقصر.

كيف يعمل التعاود

لنقل n من الأقراص من وتد البداية إلى وتد الهدف، مع استخدام الوتد المتبقي وتدًا مساعدًا: 1. انقل الأقراص الـ n − 1 العلوية من وتد البداية إلى الوتد المساعد. 2. انقل القرص الأكبر من وتد البداية مباشرة إلى وتد الهدف. 3. انقل الأقراص الـ n − 1 من الوتد المساعد إلى وتد الهدف، فوق القرص الأكبر. الخطوة 2 مسموح بها لأن القرص الأكبر يمكن أن يستقر على أي وتد. والخطوتان 1 و3 هما اللغز نفسه بقرص أقل. ينتهي الاستدعاء عند قرص واحد يُنقل مرة واحدة. وعند فكّه نحصل على 2ⁿ − 1 نقلة، ولا تضع أي خطوة قرصًا أكبر فوق قرص أصغر أبدًا.

برج هانوي عملاق في الهواء الطلق في دومين دو شانتلوب — برج هانوي العملاق في دومين دو شانتلوب. صورة: Als33120، CC BY-SA 4.0

أسطورة الأقراص الذهبية الأربعة والستين

قدّم عالم الرياضيات الفرنسي إدوار لوكا اللغز عام 1883. وروى معه أسطورة عن معبد هندي في كاشي فيشواناث، ينقل فيه الكهنة كومة من 64 قرصًا ذهبيًا وفق القواعد نفسها. وتقول الأسطورة إن العالم سينتهي عند إتمام النقلة الأخيرة. أربعة وستون قرصًا تحتاج إلى 2⁶⁴ − 1 نقلة: 18,446,744,073,709,551,615. وبمعدل نقلة صحيحة واحدة في الثانية، ليلًا ونهارًا، يستغرق ذلك نحو 585 مليار سنة. لن ينتهي الكهنة.

صورة عالم الرياضيات إدوارد لوكا — إدوارد لوكا (1842-1891)، الذي قدم اللغز عام 1883. ملكية عامة

العبها في PictorX

افتح برج هانوي، وستجد برجًا من أربعة أقراص على وتد البداية بالفعل. الحد الأدنى خمس عشرة نقلة. اسحب القرص العلوي إلى وتد آخر، أو انقر وتدًا ثم الوتد الذي تريده. المفاتيح 1 و2 و3 تفعل الشيء نفسه. يُرفض وضع قرص أكبر فوق قرص أصغر. يتراوح عدد «الأقراص» من 1 إلى 8، فيمكنك مقارنة 1 و3 و7 و15 و31 و63 و127 و255 بالصيغة. «خطوة» تعرض نقلة واحدة من أقصر حل. و«حل» يعرض الباقي. أما «شاهد 3 أقراص» فيعرض الاستراتيجية التعاودية وهي تتحرك. «تراجع» و«إعادة» يتنقلان بين نقلاتك. احفظ صورة PNG، أو افتح اللوحة في محرر PictorX.

الأسئلة المتداولة

ما قواعد برج هانوي؟

انقل قرصًا واحدًا في كل مرة. خذ القرص العلوي من وتد وضعه على وتد آخر. لا تضع أبدًا قرصًا أكبر فوق قرص أصغر. يبدأ البرج كله على وتد ويجب أن ينتهي على وتد آخر.

كم نقلة يحتاج أقصر حل؟

2ⁿ − 1. القرص الواحد نقلة واحدة، والقرصان 3، والثلاثة 7، والأربعة 15، والخمسة 31. كل قرص يُضاف يضاعف الحل السابق ويزيد نقلة واحدة.

من اخترع برج هانوي؟

قدّمه عالم الرياضيات الفرنسي إدوار لوكا عام 1883. أما قصة الكهنة والأقراص الذهبية الأربعة والستين في كاشي فيشواناث فهي الأسطورة التي أرفقها باللغز.

كم يستغرق نقل 64 قرصًا؟

2⁶⁴ − 1 نقلة، أي 18,446,744,073,709,551,615. وبمعدل نقلة واحدة في الثانية يستغرق ذلك نحو 585 مليار سنة.