You are here

The Tower of Hanoi - Myths and Maths

Andreaas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Charles Ashbacher
, on

My first detailed exposure to the classic Tower of Hanoi problem was in a computer programming class where the instructor was using it to demonstrate programming by recursion. There are three poles. The problem starts with a sequence of disks on the pole on one end, placed largest to smallest starting from the bottom. The goal is to move all of the disks to the pole on the other end, moving only one disk at a time and under the restriction that no smaller disk can ever be beneath a larger one. As long as the number of disks to move is small, it is an excellent, understandable problem that can be solved using recursive programming techniques. It also is one of the best problems in mathematical induction that does not involve operations on the integers.

The authors introduce the problem based on its history and then deal with the mathematical notation and theory behind it. Since there are very few moves that can be performed at each point, the graphs used to demonstrate the current state and the sequential moves are easy to write down and understand. Although the number of moves from opening to solution rises as the number of disks goes up, the number of options at each step remains small and easily understood.

The Tower of Hanoi is an example of a problem that is easy to state and understand, yet a thorough mathematical analysis of the problem and its extensions is lengthy enough to make a book. Even though the number of moves in a solution, given optimal play, is easily computed and proven using induction, there is enough implied mathematics in the action to make it interesting to professional mathematicians. Several theorems and propositions are presented and detailed proofs of most of them are included. Exercises are given at the ends of the chapters with hints and solutions included in an appendix.

It was surprising to learn that the “simple” problem of the Tower of Hanoi and several logical variants contain enough advanced mathematics to make a book like this and could be the subject of a full semester special topics course in advanced mathematics. The authors close with a set of open problems, proving that there is even more to learn about this problem.

Charles Ashbacher splits his time between consulting with industry in projects involving math and computers, teaching college classes and co-editing The Journal of Recreational Mathematics. In his spare time, he reads about these things and helps his daughter in her lawn care business.