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.
