The Tower of Hanoi – myths and maths. With a foreword by Ian Stewart. (English) Zbl 1285.00003

Hinz, Andreas M.; Klavžar, Sandi; Milutinović, Uroš; Petr, Ciril

Basel: Birkhäuser (ISBN 978-3-0348-0236-9/hbk; 978-3-0348-0237-6/ebook). xvi, 336 p. (2013).

This book takes the reader on an enjoyable adventure into the Tower of Hanoi puzzle (TH) and various related puzzles and objects. While essentially self-contained, readers with an introductory understanding of discrete mathematics will be more comfortable as some concepts and notation, such as mathematical logic, are assumed. The style of presentation is entertaining, at times humorous, and very thorough. The exercises ending each chapter are an essential part of the explication providing some definitions (such as perfect codes in Exercise 1.5) and some proofs of the theorems or statements in the main text. As such, the book will be an enjoyable read for any recreational mathematician but, as the authors point out, could also be used as a text book for a second course into a particular area of discrete mathematics or as an introduction for research into the various unsolved conjectures and the list of possible extension topics given in the final chapter.
Chapter 0 “The beginning of the world” begins with a detailed history of TH invented by Edward Lucas in 1883. We then move through a broad range of topics related to TH and its generalizations which equips and introduces the reader to what the book will achieve. Topics include Chinese rings, Fibonacci numbers, arithmetic (Pascal’s) triangle, combinatorics, probability, Sierpinski triangles, graphs, paths, circuits and colourings, Stern’s diatomic arrays, equivalence and Burnside’s counting theorem. Chapter 0 concludes with a thorough literature review of TH and related puzzles (there are 352 references) and their application in psychological testing.
The next eight chapters provide the mathematical detail supporting the statements and summary given in the introductory Chapter 0 and develop the known theory of TH and several generalizations.
Chapter 1 studies the ancient Chinese Rings puzzle (CR) which the authors argue was the inspiration for Lucas’ TH. Binary numbers, state graphs and use of automata are introduced. The Gros sequence (A001511) leads to paper folding, dragon curves and fractals.
Chapter 2 begins with the standard TH, described as a P0 problem of moving from a perfect state to a perfect state. If the discs are numbered from smallest to largest then the optimal solution requires moving the discs in order of the Gros sequence. Olive’s and other algorithms are given and the optimal solution is related to the CR. The authors move to P1 problems of moving from a regular state to a perfect state. An algorithm to determine if a regular state is on the perfect path is developed. Hanoi graphs are introduced and their symmetries, automorphisms, spanning trees and related codes explored. The chapter finishes with the distance between regular states and the relation to several well known (and less well known) sequences.
Chapters 3 and 4 continue the generalization to P3 problems; moving from an irregular to a perfect state. Digraphs, mixed graphs, isomorphism of Sierpinski graphs and Hanoi graphs, algorithms and automata are all applied to the problem. Chapter 4 ends with some computing applications of Sierpinski graphs and history of their topology.
In Chapter 5 the authors generalize from the three peg TH to \(n\) pegs. Beginning naturally with 4 pegs the Frame-Stewart conjecture (FSC) for minimal number of moves is given and then how numerical attempts to prove FSC have led to further conjecture. Moving to \(n\) discs on \(p\) pegs, the chromatic number, symmetry and automorphisms of the Hanoi graphs are explored. It is shown that the corresponding Sierpinski graphs embed but are not isomorphic. Numerical computing algorithms are given to explore questions such as the number of moves of the largest disc and a table of known results included, discussion of which leads to further conjecture.
Chapter 6 explores further variants with coloured discs and relaxing the “golden rule” to allow some larger discs to be placed on smaller ones. Chapter 7 looks at the Tower of London puzzle and Chapter 8 looks at oriented moves in which the state graphs become digraphs.
Chapter 9 “The end of the world” gives a light-hearted summation of the material covered followed by a list of unproved conjectures contained in the text and a list of research topics related to the TH. It is followed by a generous Hints and solutions to exercises, a Glossary and three comprehensive Indexes all of which provide the reader with as much help as anyone might wish for in a mathematical text.

Reviewer: Andrew Percy (Churchill)

MSC:

00A08	Recreational mathematics
97A20	Recreational mathematics, games (education) (MSC2010)
05-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
00-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematics in general

Keywords:

Tower of Hanoi