The Tower of Hanoi – Myths and Maths

The Tower of Hanoi – Myths and Maths

First edition
Author	Andreas M. Hinz Sandi Klavžar Uroš Milutinović Ciril Petr
Subject	Tower of Hanoi and related puzzles
Publisher	Birkhäuser
Publication date	2013

The Tower of Hanoi – Myths and Maths is a book in recreational mathematics, on the tower of Hanoi, baguenaudier, and related puzzles. It was written by Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, and published in 2013 by Birkhäuser,^{[1][2][3][4][5][6][7][8]} with an expanded second edition in 2018.^[9] The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.^[2]

Although this book is in recreational mathematics, it takes its subject seriously,^[8] and brings in material from automata theory, computational complexity, the design and analysis of algorithms, graph theory, and group theory,^[3] topology, fractal geometry, chemical graph theory, and even psychology^[1] (where related puzzles have applications in psychological testing).^[8]

The 1st edition of the book had 10 chapters, and the 2nd edition has 11. In both cases they begin with chapter zero, on the background and history of the Tower of Hanoi puzzle, covering its real-world invention by Édouard Lucas and in the mythical backstory he invented for it. Chapter one considers the Baguenaudier puzzle (or, as it is often called, the Chinese rings), related to the tower of Hanoi both in the structure of its state space and in the fact that it takes an exponential number of moves to solve, and likely the inspiration for Lucas. Chapter two introduces the main topic of the book, the tower of Hanoi, in its classical form in which one must move disks one-by-one between three towers, always keeping the disks on each tower sorted by size. It provides several different algorithms for solving the classical puzzle (in which the disks begin and end all on a single tower) in as few moves as possible, and for collecting all disks on a single tower when they begin in other configurations, again as quickly as possible. It introduces the Hanoi graphs describing the state space of the puzzle, and relates numbers of puzzle steps to distances within this graph. After a chapter on "irregular" puzzles in which the initial placement of disks on their towers is not sorted, chapter four discusses the "Sierpiński graphs" derived from the Sierpiński triangle; these are closely related to the three-tower Hanoi graphs but diverge from them for higher numbers of towers of Hanoi or higher-dimensional Sierpinski fractals.^[4][7][9]

The next four chapters concern additional variants of the tower of Hanoi, in which more than three towers are used, the disks are only allowed to move between some of the towers or in restricted directions between the towers, or the rules for which disks can be placed on which are modified or relaxed.^[4][9] A particularly important case is the Reve's puzzle, in which the rules are unchanged except that there are four towers instead of three. An old conjecture concerning the minimum possible number of moves between two states with all disks on a single tower was finally proven in 2014, after the publication of the first edition of the book, and the second edition includes this material.^[7][10]

Some of the definitions and proofs are extended into the book's many exercises.^[7] A new chapter in the second edition provides hints and partial solutions,^[9] and the final chapter collects open problems and (in the second edition) provides updates to previously-listed problems.^[4][9] Many color illustrations and photographs are included throughout the book.^[8]

The book can be read both by mathematicians working on topics related to the tower of Hanoi puzzle, and by a general audience interested in recreational mathematics. Reviewer László Kozma describes the book as essential reading for the first type of audience and (despite occasional heavy notation and encyclopedic detail) accessible and interesting to the second type, even for readers with only a high school level background in mathematics.^[4] On the other hand, reviewer Cory Palmer cautions that "this book is not for a casual reader", adding that a good understanding of combinatorics is necessary to read it,^[6] and reviewer Charles Ashbacher suggests that it has enough depth of content to be the topic of an advanced undergraduate elective course.^[2]

Although generally positive, reviewer S. V. Nagaraj complains about a "significant number of errors" in the book.^[5] Reviewer Andrew Percy calls it "an enjoyable adventure", "humorous, and very thorough".^[7] Reviewer Martin Klazar calls the book "wonderful", recommending it to anyone interested in recreational mathematics or mathematics more generally.^[9]

• Home page