Awesome Math Girls

Mihika Bansal

The Tower of Hanoi involves many mathematical concepts, two of which are recursion and fractals.

 

Recursion: 

 

Recursion helps achieve the goal of moving all the disks from the first peg to the third in the least possible number of moves. In broader terms, recursion helps break down a large problem into smaller pieces for efficiency and accuracy. For the Tower of Hanoi, recursion is specifically used to continue making “towers” until the disk with the largest radius is able to directly move to the third peg for the other disks to stack on top. Therefore, the more disks, the more moves. By using the formula S = 2n − 1 (where S is the fewest number of moves to get all the disks from the first peg to the third peg and n is the number of disks), you can find the least possible number of moves for any number of disks n without physically solving the problem. 

 

Fractals: 

 

Fractals are smaller replicas of a larger idea, another concept that comes into play with the Tower of Hanoi. For example, in nature, fractals can show up like the petals in the leaf (replicating the leaf itself)! 

The Tower of Hanoi can be expressed as a fractal too, known as the Sierpiński Triangle.

 

The Sierpiński Triangle begins with an equilateral triangle, where all the angles of the triangle are 60 degrees, and all the side lengths are equal. Then, another equilateral triangle is formed in the center, after connecting the midpoints of the larger triangle (see the biggest white triangle.) Afterward, the triangle is removed, and three smaller equilateral triangles are formed where the same process continues again to infinity. 

 

How does this relate to the Tower of Hanoi?

 

This animation on the computer (link below) shows how the Tower of Hanoi is represented in the triangle: 

https://math.ucdavis.edu/~romik/downloads/hanoi-animation.gif 

 

The bolded red line shows the fewest number of moves with four disks. There are many other possible ways, not necessarily the fewest number of moves, to solve the puzzle through the triangle from the top to the bottom right corner, zigzagging through smaller triangles.

 

References

“Tower of Hanoi.” Encyclopædia Britannica, Encyclopædia Britannica, inc., 10 Nov. 2023, www.britannica.com/topic/Tower-of-Hanoi.  

Admin. “Solving the Tower of Hanoi.” Futurum, 16 June 2021, futurumcareers.com/solving-the-tower-of-hanoi.

Jost, Eugen. Beautiful Geometry. Princeton University Press, 2017.