Skip to main content
main-content

Über dieses Buch

This is the first comprehensive monograph on the mathematical theory of the solitaire game “The Tower of Hanoi” which was invented in the 19th century by the French number theorist Édouard Lucas. The book comprises a survey of the historical development from the game’s predecessors up to recent research in mathematics and applications in computer science and psychology. Apart from long-standing myths it contains a thorough, largely self-contained presentation of the essential mathematical facts with complete proofs, including also unpublished material. The main objects of research today are the so-called Hanoi graphs and the related Sierpiński graphs. Acknowledging the great popularity of the topic in computer science, algorithms and their correctness proofs form an essential part of the book. In view of the most important practical applications of the Tower of Hanoi and its variants, namely in physics, network theory, and cognitive (neuro)psychology, other related structures and puzzles like, e.g., the “Tower of London”, are addressed.

Numerous captivating integer sequences arise along the way, but also many open questions impose themselves. Central among these is the famed Frame-Stewart conjecture. Despite many attempts to decide it and large-scale numerical experiments supporting its truth, it remains unsettled after more than 70 years and thus demonstrates the timeliness of the topic.

Enriched with elaborate illustrations, connections to other puzzles and challenges for the reader in the form of (solved) exercises as well as problems for further exploration, this book is enjoyable reading for students, educators, game enthusiasts and researchers alike.

Inhaltsverzeichnis

Frontmatter

Chapter 1. The Beginning of the World

Abstract
The roots of mathematics go far back in history. To present the origins of theprotagonist of this book, we even have to return to the Creation.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Chapter 2. The Chinese Rings

Abstract
In this chapter, we will discuss the mathematical theory of the CR which goes back to the booklet by Gros of 1872. This mathematical model may serve as a prototype for the approach to analyze other puzzles in later chapters. In Sect. 1.1 we develop the theory based on binary coding leading to a remarkable sequence to be discussed in Sect. 1.2. Some applications will be presented in Sect. 1.3.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Chapter 3. The Classical Tower of Hanoi

Abstract
This chapter describes the classical TH with three pegs. In the first section, the original task to transfer a tower from one peg to another is studied in detail. We then extend our considerations to tasks that transfer discs from an arbitrary regular state to a selected peg. We further broaden our view in Section 2.4 to tasks transforming an arbitrary regular state into another regular state. For this purpose it will be useful to introduce Hanoi graphs in Section 2.3.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Chapter 4. Lucas’s Second Problem

Abstract
In his early descriptions of the TH, Lucas pointed out the possibility of starting with an arbitrary distribution of discs among three pegs, i.e. allowing for discs lying on a smaller one. The task is again to arrive at a perfect state on a preassigned peg, while still obeying the divine rule. This, in Lucas’s opinion, will vary the conditions of the problem of the TH “to infinity”. We may even go beyond by prescribing an arbitrary, albeit regular, state as the goal. We will approach this problem in the next section and round this chapter off with a section on an algorithmic solution to Lucas’s second problem.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Chapter 5. Sierpinski Graphs

Abstract
On several occasions in Chap. 2 we realized that a different labelling for there cursively obtained Hanoi graphs \( H_{3}^{n} \) (see Figure 2.12) would be desirable. We will realize this with the same recursive procedure, yielding graphs isomorphic to \( H_{3}^{n} \), with the same vertex set, but with different edge sets.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Chapter 6. The Tower of Hanoi with More Pegs

Abstract
In Chap. 2 we have described the fundamental object of the book—the classical TH with three pegs. We have revealed its secrets and hopefully convinced the reader that it contains exciting problems with not too difficult solutions. Now, a well-known mathematical meta theorem asserts that it is easy to generalize. In this chapter we are going to study the most natural and obvious generalization of the TH with three pegs, namely the TH with more than three pegs.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Chapter 7. Variations of the Puzzle

Abstract
TH is an example of a one person game; such games are known as solitaire games. There are plenty of other mathematical solitaire games, the Icosian game, the Fifteen puzzle, and Rubik’s Cube are just a few prominent examples. Numerous variations of the TH can also be defined, some natural and some not that natural.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Chapter 8. The Tower of London

Abstract
The Tower of London (TL) was invented in 1982 by Shallice and has received an astonishing attention in the psychology of problem solving and in neuropsychology. Just for an illustration, we point out that in the paper which sets up the mathematical framework for the TL, no less than 79 references are listed! The success of the TL is due to the fact that on one hand it is an easy-to-observe psychological test tool, while on the other hand it can be applied in different situations and for numerous clinical goals.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Chapter 9. Tower of Hanoi Variants with Oriented Disc Moves

Abstract
In Chapter 6 we have introduced the concept of a TH variant and presented several such puzzles: the BWTH, additional variants with colored discs, and the BTH. We continued in Chapter 7 where the TL (and its variations) were treated in detail. In this chapter we turn our attention to the TH with oriented disc moves.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Chapter 10. The End of the World

Abstract
With the theory developed in Chapter 2 it was not very difficult to determine the age of the universe, see Exercise 2.8. Similarly, the time when the end of the universe is to be expected can be computed. The situation with the end of time is more delicate though, especially now that this book has appeared. It cannot be excluded that the Brahmins will be exposed to the book and consequently come to the idea to save some time and use one more peg—the Devil’s one. Luckily for us, the Brahmins are allowed to use only optimal strategies. Since they are men of great honor, we are safe for the time being. But there is a constant danger that the Brahmins or someone else will solve the Frame-Stewart conjecture. Then we might be faced with dramatic events in the history of the universe.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise