Introduction

The classic Towers of Hanoi puzzle (Figure 1) is known to many of us, either from our school days or as educators. The puzzle works as follows: given some number of discs (washers) of varying diameters stacked in a pyramid on one of three posts, move the stack one disc at a time to one of the other posts in as few moves as possible. The catch is that no disc can rest on top of a disc of smaller diameter. This is a wonderful problem for school age students and many people first encounter it in elementary or middle school. Though the puzzle can be presented as a thought exercise (without the physical model), having the physical puzzle enhances discovery, and as such is an essential aide in any course that discusses dynamical systems. Outside of this venue the puzzle can be used in courses from elementary school through college to teach reasoning, problem solving and the development of mathematical formulas. It can be used to discuss recursion and induction as well as graph theory with students at the secondary and college level.

The Towers of Hanoi puzzle

Given three pegs and any number of discs of increasing radius stacked in a pyramid shape on the first peg, move the stack to the third peg. Only one disc may be moved at a time and no disc of larger radius may be placed on top of a disc of smaller radius.