Many of the early Mathologer
videos had a movie hook: e to the I pi in the Simpsons, the die hard jugs
puzzle, the Futurama mind switching theorem, etc. During that time I also started
working on a doctor who based video but halfway through writing the script three blue
one brown published a video on something related. Not the same but close enough to effectively kill
the topic for a while. Happens sometime :) anyway I just stumbled across that old slideshow
and since I've got absolutely nothing else going on right now (what a joke the semester
is about to start) I decided to finish it. It's some really nice material starting
with the super famous tower of an oil puzzle but ending up well off the beaten track. I think
I first encountered the usual tower of Hanoi stuff in primary school but then throughout my life
i've learned about many other amazing aspects of this puzzle. Today I want to tell you about
some of my favorites. Among other things I'd like to tell you why the unlikely fractions 466
divided by 885 is the tower of Hanoi constant and i'd like to show you a super pretty
and super visual shortest solution of the so-called reeves puzzle which
is the four peg version of Hanoi that one there. And I'll also talk about the
so-called Frame-Stewart algorithm which is believed to give the shortest solution for
all Hanoi puzzles for any number of pegs. However although this algorithm is very natural
some expert algorithmologists - yes that’s a word - believe that nobody will be able to prove that
this supposedly shortest solution really truly is always shortest. Intrigued? Great, off we go but
first doctor who and a matter of life and death. In one of his 1966 adventures the doctor and his
friends are captured by the powerful celestial toymaker and they're forced to play a number of
life and death games involving some devilish toys. The doctor's game is an instance
of the tower of Hanoi puzzle. Here's a reminder of how you play
this game. There are three pegs and a number of discs that can slide onto each
peg. The discs start out stacked in a tower the object of the game is to move the tower all
the way to the right. And nope you can't just take all the discs and plop them on the right peg.
That wouldn't be much of a puzzle wouldn't it. The rules are that you can only move one disc at
a time. Plus a larger disc can never be placed on top of a smaller disc. Let me just show
you a few moves using the setup over there. What should you do next? Well you cannot
do this. Why? Because here disc ends up on top of a smaller disc which is against the
rules. On the other hand this is possible and this one and that's also possible here. All
clear? Great. Here's the setup in doctor who. The pegs are invisible and located at the corner
of an equilateral triangle. There are 10 discs and to win the game the doctor has to move the
tower to position b in exactly 1023 moves. The toymaker refers to the puzzle as the
tri-logic game. Whatever sounds impressive, right. I think you will lose. Can you remember
how to play. I am only allowed to move one piece at a time. That is right and you must
rearrange them in the same order that they are now on point b. And I am not permitted to put
a larger piece of the small piece correct. Ah yes the good old times :) Anyway it turns
out that the toy maker permitted the doctor just enough moves to solve the puzzle. 1023 is the
minimum number of moves to be able to relocate the whole tower and there's a unique sequence of
moves to do it. The doctor cannot afford to make a single move out of order or he'll lose the game
and his life. Okay there will be a lot of you who are very familiar with the tower of Hanoi but if
you were in the position of the doctor right now would you be able to play those exact 1023 moves
without messing up? No? I thought so and without a clear recipe in hand or in mind I doubt I could
either. So let me first quickly show you or remind you why the minimal solution has exactly 1023
moves and how you can easily execute these moves without ever messing up. And then if you are ever
captured by an evil toy maker you will be ready. Okay the key to this puzzle is to notice that for
us to be able to move the largest disc anywhere we first have to transfer all the smaller discs
to another peg, for example that one there. With the other discs on the middle peg we can now move
the biggest disc to the right peg and, actually, at this point we can complete the transfer of
our tower by moving the smaller discs again. All right how does this insight help? Well let's see. In this instance of the puzzle
there are 10 discs just like with doctor who. Let's say that M(9) is the minimum number of
moves required to move the little nine disc tower. Then we can definitely transfer the whole
10 disc tower using M(9) moves, there those, plus one move plus another M(9) moves. Okay
with M(9) being the smallest number of moves to transfer a 9 disc tower we found that we can
transfer the 10 disc tower using that many moves. But can we do any better than that? What do you
think? Well the answer is … no. Pretty obvious isn't it? If we deviate in any way from our simple
overall strategy to transfer the tower we are bound to use more moves. So what we figured out
is that the minimal number of moves to shift 10 discs is exactly this. Of course everything I just
said works for any number n not just 10. Right? And so now to figure out M(10) we just go
back up. Okay what's M(1) the minimal number of moves to relocate the little disc? Tough
one huh? M(1) is equal to well 1 of course. There one move. Okay and now we just plug
m1 equal to 1 into the formula to get M(2) there 2 times 1 is 2 plus 1 is 3. Great and just
to check there one move 2 and 3 moves in total. What are those numbers? M(1) is 1 M(2) is 3.
What's next? Well 2 times 3 is 6 plus 1 is 7. M(3) 7 then 15. Okay 31, 63, 127 looks familiar
right 255, 511 and there M(10) is 1023. Just like the toy maker planned and what are these m numbers
pretty obvious right these are just the powers of 2 minus 1. In the case of 10 discs it's 2 to the
10 minus 1 is 1023. And of course it's blatantly obvious that this works in general. The minimal
number of moves for n discs is 2 to the power of n minus 1. That's clearly the pattern. And can we
prove it? Yep it's an easy induction thing. Once we know M(n) equals 2 to the power of n minus 1
for some n discs, our stepping formula tells us that M(n) plus 1 is 2 times that plus 1, and a
little jiggle of the numbers gives this. Works the same formula. So knowing the answer for n
discs our stepping formula tells us the answer for n plus 1 discs and then we get n plus 2,
and so on to infinity. So it's all proved. It's also not too hard to show that there's
just one sequence of moves that will work for this minimum number. How can we see that?
Well again we can argue from the bottom up. Right? There is just one way to transfer
that one disc to the right using one move. What about two discs? The unique minimal way
to move the smallest disc to the middle peg together with this move together with
the second unique minimal way to move the smallest disc to the right combine into the
unique minimal way to move the two disc tower. We can continue arguing like this to convince
ourselves that there are unique ways to transfer all the towers with different numbers
of discs. There unique, unique, unique. Okay now you're the doctor and you
have to make just the right 1023 moves without messing up a single time to move the
tower. One way to get such a recipe is from a detailed analysis of the sequence of moves. This
yields for example some beautiful relationships with binary counting which is the topic of the
three blue one brown video. I'll put a link in the comments. Another way to get a good feel of what's
going on is by experimenting with smaller stacks. Let's say we've done this for a while and we
figured out the complicated sequence of moves in the case of six discs. Now let's step back
and just observe the sequence playing out in the doctor who set up viewing it from above and with
the pegs placed at the corners of an equilateral triangle. See whether something jumps out at
you while watching this pretty dance of discs. Did you notice a simple pattern? Yes? No? Have another look but this time
pay attention to the smallest disc. So what happens is that every second
turn we move the smallest disc and we always move the smallest disc in the
clockwise direction. And believe it or not these two insights are all you have to
remember to reliably execute all 1023 moves. That doesn't seem right does it? What about all
the other discs? How do we know what to do with them. Well let's have a close look. Okay first the
smallest disc moves in the clockwise direction. What comes next? Well we're not moving the
smallest disc on this turn and so there is only one possibility, this one. Okay what's next? Well
it's the smallest disc’s turn again. Moving it in the clockwise direction we get this. Okay again.
We're not going to move the smallest list so again that leaves exactly one choice this one
here. And so on. Move the smallest disc clockwise, make the only possible move that does not involve
the smallest disc, move the smallest disc, make the only possible move that does not involve
the smaller disc, and so on. Really easy isn't it it? Turns out that if you follow this recipe
you end up moving the tower to the position at the bottom left. What do you have to do if
instead your task is to move the tower from its starting position to the bottom right? Think
about it for a moment. Got it? Yep just move the smallest disc in the counterclockwise
direction instead. Pretty obvious right? Now the simple recipe for executing
the optimal move sequence in practice works for any number of discs and it's actually
very easy to prove that this is the case given the recursive nature of the algorithm. The only
thing that may change is the direction in which you have to move the smallest disc to ensure
the tower ends in the bottom left or right okay. Back to you putting yourself in the
shoes of the doctor. Which way do you have to move the tip of the tower to make sure
that the whole tower ends up in position b? Clockwise or counterclockwise? Remember your
life depends on it. How about in general? If you're dealing with n discs which direction
does the tip have to move to relocate the whole tower from a to b using the minimal number
of steps. Leave your answers in the comments. Now you should really give this a go. Get five or
six coins of different diameters and execute the algorithm. Go on i'll wait. Okay forget about it
:) did you mess up? How does the second largest disc move? How about the third largest disc?
Also share your observations in the comments. Nice stuff. There finally back to the original
tower with this side-by-side setup. To get the whole tower to the right peg what's the rule
for moving the smallest disc? Easy right? Now before I move on to the main attractions my
visualization of optimal solutions of the four peg puzzles and the elusive frame steward
algorithm, let me share some really cool insights about the original puzzle
with you that very few people know about. Okay from this starting position we can execute
one of two moves both with the smallest disc. These moves get us to two new states of the
puzzle those two here. Where can we go from these new states? Well by moving the smallest
disc we can move between these two states. We can also move to two new states all right.
If we systematically continue this picture we eventually arrive at this so-called transition
or state graph. Whoa. The vertices of the state graph are all possible states of the Hanoi puzzle
and two of these states are connected by a blue edge exactly if there is a move that takes one
state into the other state. Pretty. For four discs the graph looks like this. Cool. For five
discs it looks like this okay, and so on. These graphs are closely related to the sierpinski
triangle which you may be familiar with. But that's the story for another day. Let's get
back to our three disc state graph that one there. The starting and end states of the puzzle are
at the top and at the bottom right corner of the graph those two guys. The shortest sequence of
moves between the starting state and the target state corresponds to a straight line connection.
Nice huh? And in general any path like this corresponds to a sequence of moves that takes
you between the states at the ends of the path. Here are a couple of fun facts hiding in the state
graph. Have a look at this. This path visits every state exactly once that's pretty neat and it's
definitely a contender for a new torture puzzle if the celestial toy maker is looking for ideas. And
what's extra nice is that there is also a simple way to remember this convoluted solution. Very
similar to the way we remember the shortest path. Have a look it goes like this: move the
smallest disc to the right once, then twice, make the only move that doesn't involve the
smallest disc. Move the smallest disc left once, twice, make the only move that does not
involve the smallest disc. Now repeat, smallest disc moves right twice, other disc,
smallest disc left twice, other disc, and so on. Very nice huh? And this recipe
works for any number of discs, small right, right, other discs, small left,
left, other disc. Small right, right, and so on. This recipe also solves another Hanoish puzzle.
Add one more rule to the game that you can only move discs between adjacent pegs. Right, so you're
only allowed to move between the left and middle peg, and the middle and the right peg but never
between the left and right peg then what you see over there is the shortest sequence of moves
that takes you from the starting to the end state. Challenge for you: what's the formula for the
number of moves in this new shortest solution for the end disc puzzle over there a very
pretty answer awaits. Okay here's another interesting variation of the Hanoi puzzle. Pick
any two states. Now find the shortest sequence of moves between them. Here's one. It consists of six
moves. However shortest sequences between states are not always unique. Like in this example here's
a second shortest solution. Also six moves. Okay here's something really amazing. Do this choose
a starting state and an end state and calculate the minimal number of transition moves. Then
find the average of all these numbers. Believe it or not but somebody actually managed to find
the formula for this average minimal length. And so what? Two observations these three numbers.
The ones being raised to the power of n are all less than 1. And what happens if you take a
number less than 1 and raise it to a large power? Yep it gets tiny. This means that all these
powers tend to zero as n goes to infinity. Okay now by way of comparison it turns out that
the maximum minimal length that is the maximum possible distance between any two states is
our 2 to the power of n minus 1 from before, that one there. That is you can get from any state to any other state with at most 2
to the power of n minus 1 moves. Okay so look again the 2 to the power of
n's dominate both expressions for large n and therefore for large n the constants
minus 1/3 and minus 1 are negligible. So what this tells us is that
given a large number of discs the average minimal length is approximately
the 466/885 th of the maximum minimal length. And this makes 466/885 into something
like the Hanoi constant yep 466 divided by 885 pretty bizarre isn't it? I'm
sure you didn't see that one coming. Here's a nice puzzle for you. Remember when you
plug 3 into this formula you get approximately 3.9 for the average minimal distance. Now
obviously the exact number is a fraction right? Can you figure out what this fraction
is? Leave your solutions in the comments. So the original three peg tower of Hanoi puzzle
was published by the french mathematician Edouard Luca in 1883. It's interesting to note that Luca's
version of the puzzle actually features the pegs arranged in an equilateral triangle just like in
doctor who. Luca also considered variants of the puzzle featuring more than three pegs. Here's a
picture of what he had in mind which he published in 1889. All right now the person who usually gets
the credit for Hanoi puzzles with more than three pegs is the english puzzle master henry Dudeney
who first talked about these variants in 1896. Keen Mathologer fans will recall
that we've encountered both Luca and Dudeney previously. Among other things Luca
is the Luca and Luca numbers, the famous relatives of the fibonacci numbers and Dudeney was the
author of that tricky puzzle ramanujan solved at a glance with an infinite fraction. We just
covered the ramanujan story in a recent video. Some of Dudeney's Hanoi puzzles also made it
into his famous puzzle collection entitled the canterbury puzzles. The very first puzzle
in this collection is a four peg puzzle and I guess it's this prominent position in this
famous puzzle book that ensured serious exposure for Hanoi puzzles with more than three pegs and
led to Dudeney being credited as the inventor. Okay here's Dudeney's framing of the
puzzle. There's this group of pilgrims one of them the Reve is a smart guy who during a
rest in the town challenges his fellow pilgrims with a four-peg tower Hanoi puzzle. Here the
pegs are four stools and the discs are cheeses of varying diameters. Specifically he asks for
the minimum number of moves to transfer cheese towers consisting of 8, 10 and 21 cheeses. As part
of the solution to the puzzle Dudeney discusses solutions of Hanoi puzzles with three, four and
five pegs and among other things produces this very interesting table. For example with four
stools and 10 cheeses he claims the minimal number of moves is 49. 49 that's way less than the 1023
we needed using three pegs in the doctor who set up. On close inspection Dudeney's table hides
some surprises. For example our magical 1023 also appears in this table as the minimal number
of moves required in the case of five pegs and 56 cheeses. Also have a look at the special
numbers of cheeses done in singles out in his table in the case of four stools he considers
the numbers 1, 3, 6, 10, 15, 21 and 28. Well the regulars among you will recognize these numbers
straight away these are just the triangular numbers, numbers that can be written in the form
1 plus 2 is 3 plus 3 is 6 plus 4 is 10, and so on. For five stools the numbers Dudeney considers are
these numbers of cheeses. These are the so-called tetrahedral numbers the numbers you get when
you add the triangular numbers 1 plus 3 is 4 plus 6 is 10 plus 10 is 20. And
we get these tetrahedra. There. okay before I say anything about how Dudeney and
others attack the Hanoi puzzles with more than three pegs, let me jump straight to one of the
highlights of this video. I want to show you an easy to remember and visually stunning method
for solving the four peg Hanoi puzzles using a minimal number of moves. Perfect of course
for your next encounter with the toy maker. Okay suppose we start with six grey discs
and four blue pegs arranged like this. Six is equal to one plus two plus three and so six
is a triangular number. Arrange the six discs into three super discs like this. The smallest disc
is the first superdisc, then the next two discs together make up the second superdisc and the
remaining three discs form the third superdisc. One plus two plus three is equal to six. Now we
can just use the outer three pegs in the usual three peg solution to move the superdisc tower
around. Remember in the solution the smallest red superdisc moves clockwise and all the other
superdisc moves are forced, there, there, there. Cool but now we add the details. Let's do this
again but we'll also show the moves of the individual discs within the superdiscs that will
ensure the whole sequence is a legitimate puzzle solution. Okay red disc moves clockwise. Now
the green super disc is supposed to move here. We do this one green disc at a time using these
three pegs and the usual three peg algorithm. There, there, there the green super
disc has completed its move this means it's the little red disc turn. There. And it goes.
Now the orange superdisc is supposed to move. Here we do this one disc at a time using
these three pegs and the usual three peg algorithm. Okay this means that again
the smallest orange disc moves clockwise. One two three four five six seven moves. Okay
and by now should be clear how this continues. Orange super disc has finished
moving, little red disc moves, next the green super disc moves. Here
okay. And it goes there. One two three and finish. Excellent. A very pretty solution don't
you think. The intertwining of several optimal three peg solutions gives the optimal four peg
solution. The next triangular number after 6 is 10 so just for fun here's the complete sequence of
moves for 10 discs. If you count along you can convince yourself that the number of moves is
really 49 moves indicated in Dudeney's table. Fabulous. It's also easy to adapt this procedure
if we don't deal with a triangular number of discs. For example let's get rid of two of
the ten discs over there and we're left with eight discs. Eight is not triangular but
is also one of Dudeney's puzzle numbers. There, eight discs left over.
Create super discs as before one, two, three, etc. Now that last purple
superdisc only consists of two discs. We get rid of this defective superdisc by adding
one disc each to the last two superdiscs. There the green superdisc gets one more disc. Okay
and the orange one also gets one more disc. From now on everything proceeds as before
except that the top discs of the modified superdiscs always move counterclockwise just
quickly let's also run through this example. Great. Challenge for everybody figure out
the minimal number of moves for nine discs. Leave your answers in the comments.
For my programmer friends please implement the algorithm I just showed
you for general n. Should be fun. Dudeney claimed the numbers in his list
to be minimal. An actual proof that he was right in the case of four pegs was only
produced recently 100 years later in 2014 by mathematician Thiery Bousch. Combining
his proof with the work of others yields that the solution I showed you
is optimal. All a bit involved and much much much more complicated that you expect
knowing the simple solution for three pegs. And what about five pegs? That was proved in… well
it actually hasn't been proved. For five pegs and more we have Dudeney’s and others candidates for
optimal solutions. However there is no general proof of optimality in sight yet. In fact Donald
Knuth the algorithm guru himself once said that even if it's true that these solutions are optimal
most likely nobody will ever be able to prove it. Well Thiery Bousch did prove it for four
pegs so maybe there is hope after all. The idea for finding optimal solutions for a
certain number of pegs and discs is to base it on optimal solutions with less pegs and
or discs. It's actually quite simple. Let me show you. Say we've already figured out
the optimal solutions and numbers in this table and we're interested in the solution for
four pegs and seven discs, that number there. Okay split these seven discs into two parts. Let's
say into a blue stack of two and a green stack of five. Now we can move the green five disc
stack using all four pegs with 13 moves. Okay now we can move the blue stack of two discs
using the remaining three pegs with three moves. Finally we can move the green stick again using
all four pegs with another 13 moves. In this way we've moved the stack with 13 plus 3 plus
another 13 moves that's a total of 29 moves. Not bad. Can we do better what do you think? Well
we can split the original stack in different ways and see what happens. Repeating the calculations
for all possibilities we get these numbers here. Okay that's worse, best so
far, okay just as good, worse, even worse. So 25 is the best we can do this
way and it turns out 25 is best overall. Okay all this then also explains where those super
discs come from. Right? One of the super discs for our super pretty move sequence for seven discs is
just this layer of four blue discs at the bottom. By arguing in the same way we can keep
extending our table of numbers to the right and once enough numbers in one row have
been built up we can start building up the next row from the trivial cases involving
the smallest numbers of disc on the left. All in all a pretty straightforward
idea which definitely gives very short solutions. The algorithm that I just
described is called the Frame-Stewart algorithm. It's generally believed that this algorithm will
indeed produce minimal solutions for all possible numbers of discs and pegs. However how do you
prove that these solutions are actually shortest. Well to begin and as usual you can run some
exhaustive searches for small numbers of discs to check your conjecture. People have done that
and everything pans out so far. Then you can go pattern hunting in the algorithms to see whether
there are enough clues upon which to hang a proof. Examples of such patterns are the splitting of
move sequences into superdiscs, the special role triangular and other numbers appear to play, very
mysterious really, for different numbers of pegs, and so on. But despite the Frame-Stewart approach
being very natural and despite all the available data suggesting that Frame-Stewart is always
optimal we may have no real hope of proving that this is the case we may not see a proof of
the optimality of our algorithm in our lifetime. If you're interested in finding out more the by
far most comprehensive account of what is known about the tower of Hanoi is this book here.
At this point i'd like to thank Andreas Hinz one of the authors of this book for all his help
and in particular for answering my super tower of questions. Oh and if you're just itching for this
video to end so you can go check out doctor who and the celestial toy maker you may also want to
check out my and Marty's book on mathematics in the movies and our mathematical complement to IMDB
the mathematical movie database. There. Has got heaps and heaps of movies for you to watch. And
that's it for today. Hope you enjoyed this video. Until next time stay safe. Let me really finish
by showing you how to survive the final toy maker boss challenge. Moving our 10 discs via
five pegs using the least number of moves. This is super super cool. Instead of just
working with discs that combine into super discs as with four pegs here we work with
discs combining into super discs which in turn combine into
super super discs. Enjoy!
