Generalizing a Solution to the Tower of Hanoi with Varying Number of Pegs and Rings

Overview

Objectives The Tower of Hanoi is a problem where in a system of m pegs, n rings are on the first peg, arranged from smallest on the top to largest on the bottom. One ring can be moved at a time, and a larger ring can never be on top of a smaller one. The objective is to find the minimum number of moves needed to move all n pegs from the first peg to the last one. The Tower of Hanoi problem is valuable for it can show the most efficient way to solve problems, and it is connected to important concepts, especially mathematics, as it is related to Pascal s Triangle, used for binomial expansion, and Sierpinski's Triangle, a fractal. My evaluating criteria for this project was to find a general formula to calculate the minimum number of moves needed to complete the Tower of Hanoi given the number of rings and pegs present in the system. Methods 1.Using http://towersofhanoi.info/Animate.aspx, make a list for the minimum number of moves needed to transfer n rings for m pegs where n is an integer in the range 1-40 and m is an integer in 3-8. 2.Observe the patterns in the data, particularly how many times the minimum number of moves increases by 2 for each peg, and then how many times it increases by 4 for each peg, and so on. 3.Note that this pattern follows Pascal s Triangle, and use this fact to come up with a formula for the Tower of Hanoi. Results My results showed that increasing the number of pegs decreases the number of minimum moves required to complete the game. A pattern that all the pegs followed was that as the number of rings increase, the minimum number of moves increased by one(2^0) move for a number of times, then started increasing by two(2^1) for another number of times, then increased by four(2^2) moves, and so on. After analyzing the number of times the moves increased by one for each peg, and then two moves, and so on, Pascal s Triangle became visible as a pattern throughout. Conclusions In conclusion, I did find a formula for the Tower of Hanoi through Pascal s Triangle and combinatorics, which can be used to make a relatively simple equation.

Competition history

• CSEF 2019 Mathematical Sciences · Entry J1411

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Mathematics projects
• CSEF Mathematics projects
• Every CSEF 2019 project