หอคอยฮานอย อ งกฤษ Tower of Hanoi บางคร งเร ยกว า ป ญหาว หารเบนาเรส The problem of Benares Temple หอพระพรหม Tower of Brah

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

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

ภาพแอนิเมชันแนวทางของ**หอคอยฮานอย** สำหรับ T(4, 3)

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

ต้นกำเนิด

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

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

วิธีแก้

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

อ้างอิง

"A000225 - OEIS". oeis.org. สืบค้นเมื่อ 2021-09-03.
Hofstadter, Douglas R. (1985). Metamagical Themas : Questing for the Essence of Mind and Pattern. New York: Basic Books. ISBN .
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.
Hinz, Andreas M.; Klavžar, Sandi; Milutinović, Uroš; Petr, Ciril (2013-01-31). . ISBN .
Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. p. 137. ISBN .
(2001). 1000 playthinks: puzzles, paradoxes, illusions & games. Workman. ISBN .
Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. p. 197. ISBN .

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

เอริก ดับเบิลยู. ไวส์สไตน์, "Tower of Hanoi" จากแมทเวิลด์.

[oeis-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 .

[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). . ISBN .

[5] Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. p. 137. ISBN .

[6] (2001). 1000 playthinks: puzzles, paradoxes, illusions & games. Workman. ISBN .

[7] Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. p. 197. ISBN .