Tower of Hanoi (puzzle)
The Tower of Hanoi is a mathematical puzzle created by French number theorist Édouard Lucas in the late 19th century, often marketed as a children's toy. It consists of three vertical pegs and a set of disks of varying diameters, which are initially stacked on one peg in descending order. The objective is to move all the disks to another peg using the fewest moves possible, adhering to specific rules: only one disk can be moved at a time, and a larger disk cannot be placed on top of a smaller one.
As the number of disks increases, the puzzle's complexity grows significantly. For example, moving three disks requires a minimum of seven moves, while four disks require fifteen moves. The formula to calculate the minimum moves needed is \(2^n - 1\), where \(n\) represents the number of disks. The puzzle is inspired by a myth that tells of monks in India undertaking a similar challenge with a tower of 64 disks, a task so immense it would take eons to complete. The Tower of Hanoi not only serves as a recreational challenge but also illustrates principles of algorithmic problem-solving and recursion in mathematics.
On this Page
Subject Terms
Tower of Hanoi (puzzle)
The tower of Hanoi, sometimes called the "tower of Brahma," is a puzzle introduced by French number theorist Édouard Lucas in the late nineteenth century. The tower of Hanoi usually is marketed and sold as a children's toy. It consists of a base containing three vertical pegs and a set of disks with differing diameters. Each disk has a hole in its center so that it can be placed on any of the pegs. The object of the game is to use as few moves as possible to transfer the disks from one peg to another. It is supposedly a scaled-down version of the mythical tower of Brahma in India.
Overview
Lucas was born François Édouard Anatole Lucas in Amiens, France, in 1842. Lucas studied at École Normale in Amiens and worked at the Paris Observatory before serving as an officer in the French military. He later became a mathematics professor and taught at schools in Paris. He devoted much time to the study of the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13…) and developed the related Lucas sequence (2, 1, 3, 4, 7, 11, 18…). However, he is probably most well-known for introducing a mathematical puzzle called the tower of Hanoi in one of his many publications on recreational mathematics.
The tower of Hanoi includes a base with three vertical pegs. The puzzle begins with a set of round disks of different diameters stacked bottom to top from largest to smallest on one peg. The object is to move all the disks to a different peg in as few moves as possible. The rules dictate that only one disk may be moved at a time, and a larger disk may never be placed atop a smaller disk. Imagine the following setup: Three pegs are labeled (left to right) 1, 2, and 3. Two disks stacked on peg 1 are labeled (bottom to top) A and B. The minimum number of moves required to move the disks from peg 1 to peg 3 is three:
- First move: disk B to peg 2
- Second move: disk A to peg 3
- Third move: disk B to peg 3 (on top of disk A)
The more disks that are added, the more difficult the puzzle becomes. For example, moving three disks, requires a minimum of seven moves. Moving four disks requires fifteen moves. Moving five disks requires thirty-one moves.
The formula to determine the minimum number of moves required to solve the puzzle is 2n – 1 = x, where n is the number of disks and x is the number of moves. So, if a tower includes ten disks, 10 would be substituted for n in the formula: 210 – 1 = x, which is 1,024 – 1 = x or 1,023 = x. The minimum number of moves to move ten disks is 1,023.
The myth from which Lucas's version of the tower of Hanoi was derived suggests that somewhere in India, monks are attempting to solve the similar tower of Brahma, which has sixty-four disks. Doing so requires an exorbitant amount of moves—a number with twenty digits. It would take the monks thousands of millions of years to finish the monumental task—so long that the world would end before they could complete it.
Bibliography
Danesi, Marcel. The Liar Paradox and the Towers of Hanoi: The Ten Greatest Math Puzzles of All Time. John Wiley & Sons, 2004.
"François Édouard Anatole Lucas." School of Mathematics and Statistics, University of St. Andrews, 1996, www-history.mcs.st-andrews.ac.uk/Biographies/Lucas.html. Accessed 25 Sept. 2017.
Gardner, Martin. Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Mathematical Puzzles and Games. U of Chicago P, 1988, pp. 57–8.
Hinz, Andreas, et al. The Tower of Hanoi—Myths and Maths. Springer Basel, 2013.
Kimberling, Clark. "Édouard Lucas (1842–1891), Number Theorist." University of Evansville, faculty.evansville.edu/ck6/bstud/lucas.html. Accessed 25 Sept. 2017.
"Tower of Hanoi." Math Forum, mathforum.org/dr.math/faq/faq.tower.hanoi.html. Accessed 25 Sept. 2017.
"Tower of Hanoi." MathWorld, mathworld.wolfram.com/TowerofHanoi.html. Accessed 25 Sept. 2017.
"Towers of Hanoi." Khan Academy, www.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi. Accessed 25 Sept. 2017.