Graphs, Random Walks, and the Tower of Hanoi

Authors

Stephanie Egler, Baldwin Wallace University, BereaFollow

Abstract

The Tower of Hanoi puzzle with its disks and poles is familiar to students in mathematics and computing. Typically used as a classroom example of the important phenomenon of recursion, the puzzle has also been intensively studied its own right, using graph theory, probability, and other tools. The subject of this paper is “Hanoi graphs”, that is, graphs that portray all the possible arrangements of the puzzle, together with all the possible moves from one arrangement to another. These graphs are not only fascinating in their own right, but they shed considerable light on the nature of the puzzle itself. We will illustrate these graphs for different versions of the puzzle, as well as describe some important properties, such as planarity, of Hanoi graphs. Finally, we will also discuss random walks on Hanoi graphs.

Author Bio

Stephanie Egler graduated from Baldwin Wallace University in 2018 with a mathematics major and psychology minor. She will enter a Ph.D program in pure mathematics at Case Western Reserve University in the fall of 2018. In addition to mathematics, she has a passion for swing dancing and metal casting.

Faculty Sponsor

David Calvis

Recommended Citation

Egler, Stephanie (2019) "Graphs, Random Walks, and the Tower of Hanoi," Rose-Hulman Undergraduate Mathematics Journal: Vol. 20: Iss. 1, Article 6.
Available at: https://scholar.rose-hulman.edu/rhumj/vol20/iss1/6