The Group of Symmetries of the Tower of Hanoi Graph
Abstract:The Tower of Hanoi problem, one of the most famous mathematical puzzles, has many interesting aspects to study, such as the properties of its graph in the case of 3 pegs (the most widely known form of the puzzle) and the shortest paths (or geodesics) in generalized Tower of Hanoi problems.
In particular, Frame and Stewart, in response to Monthly problem 3918, suggested a way to narrow down the possible cases of shortest paths of the generalized problems with more than 3 pegs (this Monthly 48 (1941) 216–219); the problem remains unsolved.
In this note, we look at the generalized Tower of Hanoi problems, with the number of pegs greater than 3, from the perspective of graph theory. We prove that no matter how many pegs and disks we are playing with in the problem, the group of automorphisms of its graph is always isomorphic to the group of the peg permutations, i.e., the number of disks of the problem does not affect the automorphism group of the Tower of Hanoi graph.
Document Type: Short Communication
Publication date: 2010-04-01
More about this publication?
- American Mathematical Monthly publishes articles, notes, and other features about mathematics and the profession. AMM readers span a broad spectrum of mathematical interests, and include professional mathematicians as well as students of mathematics at all collegiate levels.
- Information for Authors
- Submit a Paper
- Subscribe to this Title
- Membership Information
- Information for Advertisers
- Terms & Conditions
- MAA Journals at ingentaconnect
- MAA Store
- Ingenta Connect is not responsible for the content or availability of external websites