Normally a tower of Hanoi looks like
three little spikes and you have
different discs on them; the aim of the
game is to move the tower from one of
the spikes to another spike.
Now I found that the spikes were holding
me back so I made this speed tower of
Hanoi so that I can-
I can get to it more quickly. So you
can't put a bigger one on top of a
smaller one, not allowed, and you can only
move them one piece at a time, so just
one piece at a time.
Actually completing it with three is
really easy, do you want to have a go? So
first one I'm going to put it here,
next one I'll move it over here,
and it wouldn't do me any help to move
this back here so I'm gonna put this one
here.
The bottom one moves, that lets us know
we're halfway.
One here,
here,
we've reformed the tower but it's in a new
position now. So I'm gonna do one with
six pieces. (Brady: You do it with flare don't you?)
The only way I know how.
So I've given each piece of the tower a
musical note, lowest note is gonna be
the biggest piece and the highest note
is going to be the top smallest piece
there.
I think the cool thing about this is I
gave it a key and so I decided the notes,
but I didn't decide the order at all,
this is the optimal solve. And it's just-
the music you're about to hear is made
by doing the optimal solve of the tower
of Hanoi.
Let's do this.
(Well done) - Okay. So I'll do it again and
you can see any patterns that you notice
coming up. So tell me, first of all what
you notice about the little piece. So
this is how to solve the tower of Hanoi.
So we're going here.
Do you notice anything about the little
piece?
Where it's going?
(It's like always going)
(from that side across to that side.) - Yeah,
uh-huh, so it follows a little a little
directional loop. If you if you labelled
the positions A B C I think
that helps. So we're going, little piece is
on A, now it's on B
now it's on C,
back to A,
now it's over to B,
C. That's one of two steps that you need
to know. So the little piece is going to
move around going ABC, so you move the
little piece. And then there's only one
other position that the next piece could
move to, so this goes to here. The little
piece you know is moving along and then
this one there's only one valid move
that you could make, so it moves along
again. There's something as well that
you might notice about the two colours. So
I've 2-coloured this - do you ever see
any of the same color touching?
(Not that I've noticed.) - No, so that's
usually how I know if I've messed
something up
is I would have the same colour touching.
So there's a parity in the tower of
Hanoi with the odd and even pieces. So
the first one, the small piece, we'll call
that an odd one because it's the piece
one;
and it's moving
from left to right from me - is that right
to left for you? Okay so it's moving
right to left. The second one, this one
here,
you might want to look at where it's
going.
So it's again-
it's moving piecewise but just slower
than this top one. And it goes from the
other direction. All of the purple pieces,
as I solve it, they're moving in a little
cycle they're going ABC, ABC. And
these pastel cloud colour pieces, they are
moving the opposite direction so they'll be going
ACB, ACB. The smaller pieces move faster.
So this one actually, every second move
is the smallest piece. Do you want me to stop
solving this now?
(It's like Rubik's cube - have you got a)
(record time?) - Oh right okay - so we should
talk a little bit about the time because
this takes- I'm working at 90 bpm. So
this takes me roughly 30 seconds to
solve a six piece tower of Hanoi. But if
you were to add more pieces to it very
quickly gets out of hand, should we go to
brown paper and calculator situation?
Discs, the number of moves, the amount
of time...
90 beats per minute. So one disc can be
completed in
one
move and
that took - what?
A second?
Less than a second.
Two discs in
1, 2,
3 moves.
That would take two seconds. Three - how
far shall we go? Four...
so six, that's how many we did.
Let's see if you can get the pattern for
the moves so that we don't have to solve
it every time. So here's three discs,
how many moves is that going to take?
1, 2, 3,
4, 5, 6,
7. I think that this should be enough
for you to see the pattern, how many
moves it takes to do the optimal solve.
It won't take me too long to do four: 1,
2, 3,
4,
5, 6, 7,
8,
9, 10, 11, 12, 13, 14,
15.
(Okay so the gap between them was 2,)
(4, 8 -)
(is the next gap going to be 16?) - Yes.
Looking at the gaps is always a really
good thing to do when you're trying to
figure out patterns. So we're going up
and we're doubling every time which
means we're going to have 2 to the power
of n. But you've got to do a bit of an
adjustment, because when n is 1
we don't have 2 -
so how are you going to fix that?
Take away 1.
Okay, so we've got 2 to the power of n
minus 1. Powers of 2 take away 1, and
that's the optimum solve, that's your
quickest way of getting this solved. 31,
64. take away 1 is
63. Okay,
cool.
Right okay so that's the first 10 - which
if you think about it would only be
this tall?
So by the time you get to something
around this tall it's taking 11 minutes
to solve. What number would you like? What
should we check out? We've done to 10.
(I feel like I want to know 100.) - 100 is a
good one, okay. So 10 to the power of 30
moves, okay. And we're doing 90 of them in
a minute so let's divide that by 90.
Okay so it's around about 2.6 times 10
to the power of 22...
years. Yep so for 100 stacks that
is how long it would take me to solve it
doing it musically at 90 bpm. You know it
would fit in this room fine. It could
logistically be done in this room. I
don't have enough time for that!
So when I'm solving the three block
optimal I go here, and here, and then my
next move following the algorithm would
be this one continues on its way. But if
I wanted, there's no rule against moving
this back here, I still have a smaller
piece on a larger piece, I'm moving one
at a time. And then I could move this
here
and this here. I mean it's not helping me
that much - and this one could go here. And
I know it's not optimal because I have
two odd pieces touching. I could then
move this one here for a while for no
reason,
put this one here, then it could go here,
back to here.
So there's a really cool way of showing
all of the different states, all of the
possibilities of
laying out these discs onto the three-
what would you call them?
Positions? So let's call our three
positions A, B and C. And right now I'm
going from smallest to largest, they're
all on position A, so I'm going to call
this AAA.
And from here I could move to BAA if I
like,
so that's an option that I have. - (So the)
(first letter is where the baby one is?)
Yeah so it goes small, medium, large.
...and large.
So I could go to BAA or
I could go to CAA. And from this position
here, CAA, I could move back to BAA, so
we're happy to link those.
So there's a nice little triangle
because all we're dealing with is the
first one right now, you know, could move.
From this vertex here, at BAA,
where can I go? So
I've already covered CAA. I can then
start moving the middle one. It can't go
here,
that's not allowed, but it could go here.
This would be called
BCA - we're going small, medium, large.
BCA.
Okay? From this vertex here, back to there,
CAA,
my options again kind of limited because
I'm moving the middle one now. can't
put it there, there's only one move I can
make - it has to go here. And so that's
going to be called CBA.
From here, BCA, where can we go? Let's have
a look.
I can move the small one and I can give
myself a CCA,
I could move the small one and go to
ACA;
and if I were to move this one here
what would that be? That would be BAA
which is going back up along the route
so we don't need to show that one. So
it's only the small one moving that
makes sense here, I've got my two options.
ACA- and I can swap between these two
as well
so I can put a line in there. I think- I
think once we fill in what can happen
here you might start to recognise
something?
When I've got them stacked up at this
ABA position - A B A. I could move this one
if I want as well,
that's got a free space, and that
would give me ACA which is already on
this graph so I can join those together.
And at this point
you maybe start to notice what's going
on here.
(You obviously are noticing it.)
The ever ubiquitous.
- (It's totally ubiquitous, I can see it on your jumper!)
Yeah we've got a Sierpinski triangle
situation here.
Will I fill this in for the other
options?
BBB
And that would be a solve. So that's them
all stacked up in a different position.
So CCC, that's a solve as well.
And just the way that
a Sierpinski triangle works,
the size is going to be 2n. So this
length here
will be
2 to the power 3, which is 8;
and because you're already starting
on 1 - you're already here - so it only
takes you 1, 2, 3, 4, 5, 6,
7, and then you're at your solved
position. So that that is where your 2
n minus 1 comes from. And I mean, if you
wanted to take a really leisurely stroll
around the tower of Hanoi - you know,
you're not in a rush to get from A to C
and solve it all - there is a way to go
around every single one of them.
So we're starting here, we're going to go
along here,
take a little detour into there...
CCC, so that's your longest route and
then if you want to go back to where you
started -
Yeah, so this is a cyclical way of
getting around all of the possible
positions in your tower of Hanoi, it's a
Hamiltonian path. And if you can see it
drawn out, it's called the Sierpinski
arrowhead. I love it, it's a beautiful fractal.
Thanks to Brilliant for supporting
today's episode;
and what a ray of light Brilliant is
with its interactive courses, daily
challenges, quizzes - all sorts of great
stuff to expand your mind and keep you
entertained.
Everything's lovingly designed to make
sure you're engaged, to keep you
thinking, to keep you clever! It's really
good looking,
easy to use; it's made by people who care
and who are serious about making the
world a better place.
If you've already got it, why not
consider Brilliant as a gift for the
other curious minds in your life?
There's even 20% off a
premium subscription by going to
Brilliant.org/Numberphile
the address there on the screen.
Check them out, you will not be
disappointed.
Check out the links in the video
description, we've got a bit of bonus
footage on our Numberphile2 channel -
behind the scenes on the recording of
our tower of Hanoi video - and there are
also links to Ayliean's work on social
media. She's especially big on TikTok
I'm led to believe, but she's doing
really great stuff so check it out.