Key to the Tower of Hanoi - Numberphile 

I think we might have a new “neatest brown paper” champion.

It's one of those puzzles which the longer you analyze it, the more amazing properties you find. That Sierpiński triangle really surprised me!

Haven't watched Numberphile in a while, now there's a scottish person wearing a fractal hoody talking about my favourite maths puzzle? Feels good to be back.

That was one of the best videos I’ve seen in a while. Love this hidden art in math stuff.

My favourite solution is to assign each ring to a digit of binary and start counting from zero, every time you switch a digit from 0 to 1 you move that corresponding ring to the next available spot. This also gets you the optimal solution. This also shows very obviously why the solution is based on powers of two and that each piece moves twice as often as the next largest ring.

Waaaaaay back in 1979 I wrote a program to solve arbitrary size towers of hanoi puzzles in BASIC for my Computer Studies O level course work :) I've always had a soft spot for this puzzle.

I literally cannot get over how perfect the optimal tower of hanoi solve fits into 4/4 time with a single beat always missing at the end perfection

Please get Ayliean back on the channel… never thought about a tower of Hanoi musically before and have to say I could listen to it all day! Thanks for the great content :)

First ever Tower of Hanoi video ever to not mention recursion! Also the most musical one...

That was great - more from Ayliean please! Loved the secret jumper spoiler.

Me 5 seconds into the video: Ooh cool jumper she's wearing Me at 10 minutes into the video: HEY WAIT A MINUTE

I absolutely loved it. Ayliean is so incredibly enthusiastic about the puzzle that it's contagious - you can literally feel her joy as she talks about it

I cannot believe it. Our professor showed the tower of Hanoi problem to us this morning. What a coincidence!

I love it when patterns are easier to detect musically/rhythmically rather than visually.

My favourite incidence of this puzzle is when it cropped up in Professor Layton while I was relaxing after a long day on a business trip. It was the one night of my life I have spent *in* Hanoi.

I love how Numberphile can be so relevant to my life at times. I planned an activity around the Tower of Hanoi concept the other day so it was great to see it analysed in video!

I've never drawn the state-space graph of the Hanoi towers. Had no idea it has something to do with Sierpinsky triangles. Thank you :-)

This is so beautiful! Definitely one of my favorite videos from Numberphile!!

I love how this made like 5 new connections about concepts I already knew.

Me seeing this video in my feed: Cmon it's a matter of odds and evens. Me finishing this video: Mind blown.

When you did it again without the music, the notes played in my head automatically and I love this so much....this gives me such an appreciation for the makers of this video

You know you've found a real mathematician when they stop to think about 64 minus 1. "Now, what number system are we using...?"

I love arpeggios, and I gotta say that optimal solve slapped.

I never knew how to play this when I was young. I just thought it's supposed to be stacked randomly for fun

Great episode! I love the "visualisation" using music. What is that called? Audiation?

She's great, hope to see more of Ayliean in the future.

Omg best Numberphile yet, love your content Ayliean

Now I can compose music without any music lessons. Thank you.

Love the Tower of Hanoi! It's so simple and profound. I keep learning things from it and it seems that the learning can never stop!

*flashbacks of the tower of Hanoi puzzle from the Noveria mission in Mass Effect 1*

I can't believe they didn't explain *why* all these elegant mathematical relationships are there. Let's take the 6 tower as an example. When you want to solve that, how do you do it? You need to move the base from the spot it's on (let's call that A) to the new spot (C). To do that you need to move all the ones above it off and restack them on spot B. Then, once you've moved the base to C, you can restack everything else again, but this time on C as well. So to solve a 6 height tower, you're solving the 5 tower, moving the base, and solving the 5 tower again. And when you solve the 5 tower, you're really solving the 4 tower twice, and so on. That's why each new disk doubles the time it takes to solve it. That's why the Sierpinski triangle map works: a Sierpinski triangle is composed of a smaller Sierpinski triangle on top (solving the n-1 tower the first time) and two more on each side (solving the n-1 tower the second time, but either in the B or C slot). Both the Hanoi tower and Sierpinski triangle are self-similar, i.e. made up of smaller versions of themselves. It's why you get those patterns in the movement of each disk. I think the math is a lot more beautiful when you explain why it all works

Have you noticed that this starts with the Dies Irae? The first four notes, C B C A, are a very famous and very old theme that is called “Day of Wrath” in Latin and is often found associated with death in movies!

This was so good! I hope we get to see Ayliean again. The jumper tie-in made me so happy haha

I learned the proof in Further Maths - we now play the game with Year 6 students joining our school to see if they can notice any patterns. UKC does it as part of their secondary school enrichment days too. Kids seem to love it!

I did not expect this video to be so interesting. I thought, Tower of Hanoi, done to death, but no, this kicked the door down.

Ah dang, she pulled a sneaky one on us! I thought that was just a cool shirt!

Loved the musical element to this demonstration. We had an eight-piece tower growing up in the 1970s. All the wooden disks were brown. PS - She has beautiful penmanship.

1:18 My brain kinda expected the music to go for 2 more notes

I love things that unexpectedly end up being the Sierpinski triangle.

This was the most intuitive explanation of Towers of Hanoi I've seen so far. Back when I was taking Computer Science at school, I learned about the Towers of Hanoi, but my teacher never quite managed to communicate how exactly to solve them, other than stating "you need recursion to solve this problem". He never really elaborated on that much further and I've never quite grasped that. I think I understand a lot better now.

This is fantastic. Tempted to go plug a few instances of this pattern into my sequencer and see what comes out of the synths...

This is the most amazing video on tower of hanoi!! OMG how crystal clear explanation!!!

It’s actually a pretty nice puzzle to try and figure the method to solve it by yourself. I remember doing that in problem solving class in middle school. It is not as hard as it looks, you just have to spend some time

Brilliant! Thank you!

That musical note thing was absolutely amazing.

This was the project I did a week ago! I solved it by using an algorithm where odd-numbered discs must sit on even-numbered discs. In case there exists an empty peg, the disc must be moved there. Like that.

Wow. Thee music of that alone gave away the inevitability of the solution.

A great episode Brady. Thanks to you and Ayliean! This was a novel take (for me) on Towers of Hanoi. The graph representation of the permissable moves is so interesting!

Kudos to the editor for audio & video note work

Every time i come upon these in a video game from now on I'm gonna watch this video again 👍👍👍

I knew it from the start that Sierpinski Triangle will come up. I mean, I’m old enough to notice how thoughtful mathematician with their tee shirt. Amazing video btw, great representation using notes on tower of Hanoi Love it!!!

Beautiful way to show this puzzle. Now I know Ayliean and after a few videos of her on TikTok I'm listening "The Less I Know The Better" what a nice afternoon :) Thank you for all your excellent work.

WoW! That a puzzle I did as a kid ends up generating a Sierpiński triangle... AND in a way that I can actually UNDERSTAND... mind blown!

That music sounded really good, thanks!

Super great video ! The idea of using a tune to materialize the moves of each block was brilliant ! Another proof maths and fractals can turn musical !

I learned most of this from experimentation, but learning its shape and mathematics was truly enlightening. Thanks for sharing!

I thoroughly enjoyed that. I had no idea where it was going at the start.

As soon as I saw her shirt, I was thinking: "Oh, it is going to be one of THOSE!" - I was not disappointed. Great video. I love seeing familiar things pop up in unexpected ways :)

The Tower of Hanoi was the subject of a classic Doctor Who episode in 1966 and I remember discussing with my maths teacher at school the optimal solution (without music) which I had worked out.

Mind blown each time this is explained.

That's also really cool because you can see how the Serpinski triangle keeps growing as you add more disks! Imagine adding an A to the end of every node of the one MacDonald drew out, which would represent having 4 disks, and then starting from the BBB and CCC corners (now BBBA and CCCA), you can now move the bottom disk - and from there you get identical copies of the original triangle except now the last letter is something else - BBBA opens up BBBC (and a copy of the original triangle with "C" as the last letter) and CCCA opens up CCCB (and the "B" ending triangle!)

This is very interesting and engaging. Well done!

Thanks!

Thank you

Mathologer's video on the topic is highly recommended. It's called "The ultimate algorithm".

It's been a while since we last had a new face on Numberphile. Great video in every way!

Watching you solve it with musical notes was beautiful.

this was great!!

It gives you goosebumps when she is unfolding Sierpiński triangle. Math is awesome

Very cool. Love the music. thanks for posting! :D

7 with 127 steps could be pretty interesting musically. Certainly gonna work that one out on my guitar. Should shred something wicked at 127 bpm and a gnarly fuzz! Gonna take some practice though... 3Blue1Brown did one on Tower of Hanoi too. The optimal solve is the same as counting up to 15 in binary.

its actually quite simple There are a total of f(N+1)=2f(N)+1 operations that needs to be done This hanoi works in a recursive manner. To move every disk from 1st location to 3rd location for N+1 Disks you would need to apply below 3 steps in a recursive manner: 1-You would first solve the problem for N disks and move all of them to 2nd location. (f(N) operations) 2-You would move the N+1th disk to third location (1 Operation) 3-You would move N disks on the 2nd location to 3rd location. (f(N) operations)

Putting it to musical notes was interesting. I kept thinking about the preserved segment from one of the lost Dr. Who episodes where the Dr. is challenged by the Toy Master who challenges him to the Tower of Hanoi in 10 steps.

WOW. From Hanoi tower to Serpinski triangle and Hamiltonian path. Mind-blowing.

it would be neat if we could hear the musical sequence for a 12-disc solve so we could hear what it sounds like with all the notes of the 12-tone equal temperament system

Thank you! I did the musical notes, using a pentatonic scale and six disks, and programmed a four-track synthesizer with different note values for each track, 1/8, 1/4, 1/2, 1. It sounds so cool.

I had an exhibition and I'm in the maths club Your video made me easy to do it Thank u soo much❤❤❤

We programmed the problem in class a week ago, its really simple using recursion.

The musical representation of the optimal solve was brilliant!

That was beautiful and inspiring ❤️😊

I am actually born in Hanoi, and so happy that have a puzzle named it. And now that puzzle is actually on Numberphile, one of the best Math RU-vid channels ever. I can't believe that this can happen!

Your hair is amazing, and it matches perfectly with your tower😍

The moves also increase in a 2x+1 Pattern where x is the moves it take for the previous number of disks.

That puzzle must be way harder when you're trying to solve it in time with the music! I like Ayliean's accent; it takes me right back to my youth.

This was too short 😫 lovely episode ❤

Cool shooting location, Brady!

that sounds incredible!

How on earth can so many people dislike this video?! It's brilliant! Great upload, thank you.

Move the tower above the largest disc (may be a tower of 0 discs) to the spot that is not the destination, move the bottom disk to the destination, then move the remaining tower to the destination. This is actually enough of an algorithm to solve it. Just apply it recursively. Or, to make it a bit simpler to understand: If we are starting in A and need to go to C, the bottommost disc needs to go to C, the one above to B, the one above that to C, and so on.

This made my day 🎶

I love these math nerds that are super nerdy to a very very specific sub category and are so passionate about it. Reminds me of the guy with a basement full of Prince Rupert drops. Meet one of these beautiful bastards early enough in life and you're a math nerd too for ever!

I really liked this episode

I would love to hear a version of that piece walking down the whole scale.

I usually just think of this puzzle inductively. If you need to move an n-stack from position 1 to position 3, simply move the top (n-1)-stack to position 2, then move the bottom piece to 3, then the (n-1)-stack to 3. This gives the same solution but its easier to remember and easier to reconstruct if you forget (though maybe worse for speed solving?).

Always love it when Math + Music are combined.

its so cool seeing how maths patterns translate into different forms of itself, from numbers to nature to music. its so cool. almost would be cool to have a small 100 hour stack sitting in a room as a symbolic sculpture, a reminder upon looking at it of the hard to imagine time something you can so easily see could take.

the sonified result sounds a lot like the main theme of Michel Corrette's first concerto for organ!

Great video

Another game could be to start with the stack alternating colours, use 4 pegs/spaces and aim to build two towers, each containing all of one colour.