There must be millions of people who have heard of the Tower of Hanoi puzzle and the simple algorithm that generates the simplest solution. But what happens when you are playing the game not with three pegs, as in the original puzzle, but with 4, 5, 6 etc. pegs? Hardly anybody seems to know that there are also really really beautiful solutions which are believed to be optimal but whose optimality has only been proved for four pegs. Even less people know that you can boil down all these optimal solutions into simple no-brainer recipes that allow you to effortless execute these solutions from scratch. Clearly a job for the Mathologer. Get ready to dazzle your computer science friends :)
I also talk about 466/885, the Power of Hanoi constant and a number of other Hanoi facts off the beaten track. And the whole thing has a Dr Who hook which is also very cute.
00:00 Intro
01:58 Chapter 1: The doctor vs. the toymaker
14:27 Chapter 2: Hanoi constant
21:21 Chapter 3: The Reve's puzzle
28:04 A beautiful shortest solution for 10 discs and 4 pegs (discs and super-disks)
30:23 Chapter 4: Unprovable algorithm
35:43 A beautiful shortest solution for 10 discs and 5 pegs (discs, super-discs and super-super-discs)
37:17 Supporters
Here are some references for you to check out:
Andreas M. Hinz et al. - The Tower of Hanoi – Myths and Maths, 2nd edition (2018, Birkhäuser Basel) That's the book I mentioned in the video.
The Dr Who episode (well the part that's not been lost) [ Ссылка ]
The 3Blue1Brown video that I mention [ Ссылка ]
Thierry Bousch, La quatrième tour de Hanoi, [ Ссылка ]
That's the paper that pins down things for four pegs.
Andreas M. Hinz, Dudeney and Frame-Stewart Numbers,
A nice paper explaining the connection between Dudeneys's work and Frame-Stewart. Also worth reading for the historical details. [ Ссылка ]
A. van de Liefvoort, An Iterative Algorithm for the Reve's Puzzle, [ Ссылка ]
I found this one useful.
Paul K. Stockmeyer, [ Ссылка ] A couple of very nice papers including a huge bibliography.
Ben Houston & Hassan Masum, Explorations in 4-peg Tower of Hanoi, tinyurl.com/mw95tnek This paper has some pictures of state graphs for the 4-peg puzzle.
[ Ссылка ] Very fancy animation of mulit-peg tower of Hanoi. Sadly, it just comes across as a mess of moves for more than three pegs. Programmers, you really should rise to my challenge to animate the 4-peg algorithm the way I present it in this video.
Here is the link to the wiki page for the Celestial toymaker Dr Who episode [ Ссылка ]
Makes very interesting reading. Especially the fact that most of this episode has been lost I find pretty amazing. That's also why I only show a still image from the relevant part of the episode and play some audio snippet.
Music: Fresh Fallen Snow and Morning Mandolin both by Chris Haugen, Mumbai effect. All from the free YouTube audio library.
Enjoy!
Burkard
