หอคอยฮานอย

จากวิกิพีเดีย สารานุกรมเสรี
(เปลี่ยนทางจาก หอคอยแห่งฮานอย)
ชุดของเล่นหอคอยแห่งฮานอย (จาน 8 แผ่น)
ภาพแอนิเมชันแนวทางของหอคอยฮานอย สำหรับ T(4, 3)

หอคอยฮานอย (อังกฤษ: Tower of Hanoi, บางครั้งเรียกว่า ปัญหาวิหารเบนาเรส (The problem of Benares Temple)[1], หอพระพรหม (Tower of Brahma) หรือ หอคอยของลูว์กา (Lucas' Tower)[2] และบางครั้งเรียกสั้น ๆ ว่า ปริศนาพีระมิด (pyramid puzzle)[3]) เป็นเกมคณิตศาสตร์หรือปริศนาที่มีเสาสามเสาและจานที่มีเส้นผ่านศูนย์กลางที่ต่างกันซึ่งเจาะรูปตรงกลาง โดยวิธีเล่นจะเริ่มด้วยการตั้งจานทั้งหมดที่ด้านหนึ่งเรียงลำดับตามขนาด โดยอันเล็กสุดอยู่ข้างบน ทำให้เป็นรูปร่างกรวย เป้าหมายของปริศนานี้คือย้ายจานทั้งหมดไปยังเสาอันสุดท้าย โดยต้องทำตามกฎนี้:

  1. ย้ายได้เพียงหนึ่งแผ่นเท่านั้น
  2. ย้ายแผ่นบนไปยังแผ่นอื่นที่มีขนาดใหญ่กว่าหรือบนเสาที่ว่าง
  3. ห้ามวางแผ่นที่ใหญ่อยู่ด้านบนแผ่นที่เล็ก

ในเกมที่มี 3 แผ่น สามารถทำได้ภายใน 7 ครั้ง จำนวนครั้งน้อยที่สุดที่เป็นไปได้สำหรับการย้ายจานบนหอคอยฮานอยคือ 2n − 1, โดย n คือจำนวนจาน

ต้นกำเนิด[แก้]

นักคณิตศาสตร์ชาวฝรั่งเศส เอดัวร์ ลูว์กา นำปริศนาหอคอยฮานอยเข้าสู่ตะวันตกใน ค.ศ. 1883 ทำให้มีตำนานมากมายเกี่ยวกับธรรมชาติอันเก่าแก่และลึกลับของปริศนาปรากฏขึ้นแทบจะทันที[4] ซึ่งรวมตำนานหนึ่งเกี่ยวกับวิหารกาศีวิศวนาถในอินเดีย ซึ่งมีห้องขนาดใหญ่ที่มีเสาเก่าสามเสาอยู่ในนั้น กับจอนสีทอง 64 แผ่น ตามคำทำนายของพราหมณ์ว่า บรรดาพราหมณ์ได้ย้ายจานเหล่านั้นไปตามกฎที่ไม่เปลี่ยนแปลงของพระพรหมตั้งแต่นั้นมา ทำให้ปริศนานี้มีอีกชื่อว่า หอพระพรหม ตามตำนาน เมื่อมีการวางแผ่นสุดท้าย โลกก็จะถึงจุดจบ[5]

ถ้าตำนานเป็นจริง และถ้าบรรดาพราหมณ์ย้ายแผ่นเหล่านี้ในอัตรา 1 แผ่นต่อวินาที โดยใช้จำนวนครั้งน้อยที่สุด จะต้องใช้เวลา 264 − 1 วินาที หรือเกือบ 585,000 ล้านปีจึงจะเสร็จ[6] ซึ่งมากกว่าอายุจักรวาลในปัจจุบันประมาณ 42 เท่า

วิธีแก้[แก้]

ปริศนานี้สามารถเล่นด้วยจานกี่แผ่นก็ได้ ถึงแม้ว่าของเล่นส่วนใหญ่จะมีประมาณ 7 ถึง 9 แผ่น จำนวนครั้งน้อยที่สุดที่เป็นไปได้สำหรับการย้ายจานบนหอคอยฮานอยคือ 2n − 1 โดย n คือจำนวนจาน[7]

อ้างอิง[แก้]

  1. "A000225 - OEIS". oeis.org. สืบค้นเมื่อ 2021-09-03.
  2. Hofstadter, Douglas R. (1985). Metamagical Themas : Questing for the Essence of Mind and Pattern. New York: Basic Books. ISBN 978-0-465-04540-2.
  3. Cohn, Ernst M. (1963). "A device for demonstrating some elementary properties of integers". The Mathematics Teacher. National Council of Teachers of Mathematics. 56 (2): 84. doi:10.5951/MT.56.2.0084. ISSN 0025-5769. สืบค้นเมื่อ 9 March 2021.
  4. Hinz, Andreas M.; Klavžar, Sandi; Milutinović, Uroš; Petr, Ciril (2013-01-31). The Tower of Hanoi – Myths and Maths. ISBN 978-3034802369.
  5. Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. p. 137. ISBN 978-0-03-084693-9.
  6. Moscovich, Ivan (2001). 1000 playthinks: puzzles, paradoxes, illusions & games. Workman. ISBN 978-0-7611-1826-8.
  7. Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. p. 197. ISBN 978-0-8218-4814-2.

แหล่งข้อมูลอื่น[แก้]