Key to the Tower of Hanoi - Numberphile

Featuring Ayliean MacDonald... Check out Brilliant (get 20% off their premium service): brilliant.org/numberphile (sponsor)
More links & stuff in full description below ↓↓↓
Extra footage from the making of this video: • Tower of Hanoi (extra)...
More about Ayliean MacDonald: linktr.ee/Ayliean
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from Math For America - www.mathforamerica.org/
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Additional sound design by Alan Stewart
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9

[@Rubrickety]

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

[@Affews100]

That handwriting, so amazing

[@callumroy8899]

For sure a podium place

[@user-lk3zc8xj4m]

Who is the old champion? Fedrico?

[@GraniteGeek]

My thought, as well: A great video ("Serpinski Arrow" - cool!) with truly excellent handwriting

[@dtitco69]

That is indeed very tidy brown paper

[@pyglik2296]

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!

[@telectronix1368]

I was trying to work out what the pattern would be for a 4 disc tower rather than the 3 used there.

[@Fanny-Fanny]

klaatu barada nikto

[@SpencerTwiddy]

@@telectronix1368 it’s a bigger Sierpinski triangle (4th iteration)

[@YOM2_UB]

@@telectronix1368 Start with an n ring graph. To construct an n+1 ring graph: - Place an n graph at the top, with A appended to each vertex string. - Take another copy of the n graph, append B to each vertex, rotate it 120 degrees clockwise, and place it to the bottom-left. - Take a third copy of the n graph, append C, rotate it 120 degrees counter-clockwise, and place it to the bottom-right. - Add three edges connecting: - the A graph's bottom-left vertex with the B graph's top vertex - the A graph's bottom-right vertex with the C graph's top vertex - the B graph's bottom-left vertex with the C graph's bottom-right vertex

[@ygalel]

IKR Absolutely mindblowing

[@egalomon]

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.

[@steamer1]

Not a hoodie. Sorry for being Hanoing.

[@robertveith6383]

* Scottish

[@vigilantcosmicpenguin8721]

I like how the fractal t-shirt was foreshadowing.

[@rjrastapopoulos1595]

Same here.

[@MissionHomeowner]

The Scotch are a strange people, so loving towards England they voted against freedom from it. They are not yet ready for self-government, but they are great at explaining things.

[@thatoneginger]

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

[@numberphile]

Cheers

[@1994AustinSmith]

Immediately clicked when mentioned how much the smallest piece moves.

[@Triantalex]

??

[@Escher99]

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.

[@ancientswordrage]

That would make a great video

[@denny141196]

@@ancientswordrage Boy, do I have news for you. Go look up 3b1b's video on the same topic

[@kantpredict]

I immediately thought of binary when I heard the musical pattern. I taught myself to count on my fingers in binary a while ago but have since forgotten...

[@g.ricepad9470]

Fun fact: this has an application on Super Mario 64 A button challenge

[@YOM2_UB]

@@g.ricepad9470 Do tell.

[@Xcyiterr]

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

[@jnbplaysgames]

Plot twist: last note is a half note 😉

[@IanSlothieRolfe]

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.

[@numberphile]

Nice one.

[@Nick_Scouts]

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 :)

[@ZandarKoad]

Do you have a link to an hour long (or long) Tower of Hanoi KZbin music version?

[@lukasmiller8531]

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

[@Toobula]

In my opinion, not showing the recursive solution makes everything else pointless. The recursive solition is the very soul of the puzzle.

[@kwesisalim]

Why mention when you can show the beauty of recursive thinking. A simple pattern solving complex problems with attractiveness and soul. Can you dig it?

[@neiljf1089]

It doesn't mention recursion directly but it is implied by the fact you get a fractal structure

[@pectenmaximus231]

@@Toobula there are so many videos covering the recursive solution, so I think this acts as a complement, rather than treading same ground and turning 14 minute video into say a 20 minute video

[@c.james1]

@@Toobula Computerphile already covered it quite a while ago, so why would they retread the same stuff... better to add to the discussion.

[@andreareali8593]

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

[@MrCommentGod]

Cool

[@subliminalvibes]

You'll notice a global "curricular trend" amongst your favourite KZbinrs from time to time.

[@lukasmiller8531]

Did you look at recursion or time complexity?

[@karthikwasudevan]

@@subliminalvibes why is that?

[@deathhog]

Coincidentally, I was thinking about the tower of Hanoi last night as well. "How do I calculate the minimum number of moves... I never did bother to figure that out as a kid."

[@Zveebo]

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

[@murphygreen8484]

+

[@tomrivlin7278]

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

[@davidlyford-tilley1598]

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.

[@szkoclaw]

Uhm, Google knows where you are/

[@davidlyford-tilley1598]

@@szkoclaw Sure, but Professor Layton on the DS doesn't :p

[@CrazyDW00]

Never will I see this puzzle and not think of stacks of pancakes…

[@pratyushkumarsahoo8591]

Which Layton Game it was?

[@TheRabbitPoet]

@@pratyushkumarsahoo8591 Pandora's box if I'm not mistaken

[@saladfingerpl]

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

[@digitig]

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

[@SpencerTwiddy]

Actually, in all number systems 64 - 1 is still written 63

[@SpencerTwiddy]

The value of the number depends on base, and we could be in any base above seximal

[@digitig]

@@SpencerTwiddy Oh, if you only have to worry about *base*, sure... :)

[@SpencerTwiddy]

@@digitig I guess. I might have missed the joke in your comment, but to me I feel like not doing 64-1 quickly is exactly what a NON-mathematician would do

[@TheBlueArcher]

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

[@Matthew-bu7fg]

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!

[@Joey-rs7uq]

Its probably the youtube algorithm buying info from your facebook or something. xp

[@danieledstrom5777]

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

[@MateHegyhati]

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 :-)

[@vigilantcosmicpenguin8721]

Wow, I thought everyone in the world had drawn the state-space graph of the Hanoi towers!

[@Sam-oz8pn]

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

[@SpencerTwiddy]

3Blue1Brown already has a video on exactly this!

[@MrAlRats]

@@SpencerTwiddy Which one?

[@SpencerTwiddy]

@@MrAlRats It's a 2-part video titled "Binary, Hanoi, and Sierpinski" imo the best ever made on the subject

[@mathwithjanine]

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

[@numberphile]

Thank you

[@Sarah-re7cg]

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

[@appropinquo3236]

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

[@Ekevoo]

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

[@WestExplainsBest]

The great thing about math is the number of connections that can be made. Its beauty comes from the complexity derived from perceived simplicity!

[@SaveSoilSaveSoil]

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!

[@timothywalsh866]

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

[@musik350]

Sonification :)

[@peterhansen5804]

Notification ;-)

[@felipevasconcelos6736]

It’s called sonification or auralization.

[@VictorGauto]

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

[@walkingwriter4325]

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.

[@XLatMaths]

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!

[@SpencerTwiddy]

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!

[@SpencerTwiddy]

Hear for yourself at 1:42 - 1:45

[@RPG_Hacker]

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.

[@shadowshedinja6124]

It's recursive because in order to move the bottom piece of a Tower of Hanoi of size N, you must first move all of the other pieces into one stack, which is the same process as solving an N-1 tower. Once you move the bottom piece, you solve the N-1 tower again.

[@1994AustinSmith]

@@shadowshedinja6124 Knowing the human trick to it, I'd just loop (psudo-code) Starting from left peg $smallest = left(odd)/right(even) 1 If peg left of $smallest is greater/less than peg right of $smallest {next valid move} Repeat

[@AYUSHKUMAR-uk1tr]

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

[@callumroy8899]

Omg best Numberphile yet, love your content Ayliean

[@hengirmen]

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)

[@lepannean4231]

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

[@pectenmaximus231]

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.

[@bassism]

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

[@almoglevin]

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

[@saimohnishmuralidharan5440]

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.

[@GreenFoxLuama]

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

[@kwesisalim]

The philosophy in this quote is amazing!

[@vigilantcosmicpenguin8721]

Ah, to be young and carefree.

[@ThatGuyMagnum]

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

[@SpencerTwiddy]

There weren’t any arpeggios in it but it did sound pretty🤪

[@ajbiffl4695]

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!)

[@Scuud52]

Brilliant! Thank you!

[@avi12]

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

[@nickwisely2581]

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!!!

[@alasdairhunter9870]

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!

[@namankeshari7332]

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

[@holgerchristiansen4003]

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 :)

[@ShabbaDabb]

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

[@unkiwii0]

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.

[@RobG1729]

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.

[@Zhaggysfaction]

That musical note thing was absolutely amazing.

[@JonBastian]

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

[@JacksMacintosh]

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

[@olivierdebever7952]

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 !

[@numberphile]

Thanks

[@vaakash]

Kudos to the editor for audio & video note work

[@LouigiVerona]

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

[@josepedrocoimbra8007]

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

[@barthennin6088]

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!

[@alphonsajohnson2657]

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

[@adityavardhanjain]

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

[@Denis_Bobrov]

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

[@peterkelley6344]

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.

[@seth333]

Thanks!

[@MohammodnazmuSakiB]

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

[@JoseArrieta]

Thank you

[@larryscott3982]

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

[@CthulhusDream]

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

[@bemusedindian8571]

Mind blown each time this is explained.

[@awandererfromys1680]

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.

[@ZandarKoad]

Do you have a link to a lengthy musical rendition of this? Would love to listen while I'm working...

[@awandererfromys1680]

@@ZandarKoad No, and I can't garantee anything really. Got no decent recording hardware atm. But here are all 127 notes, for whoever is interested: C-D-C-E C-D-C-F C-D-C-E C-D-C-G C-D-C-E C-D-C-F C-D-C-E C-D-C-A C-D-C-E C-D-C-F C-D-C-E C-D-C-G C-D-C-E C-D-C-F C-D-C-E C-D-C-B C-D-C-E C-D-C-F C-D-C-E C-D-C-G C-D-C-E C-D-C-F C-D-C-E C-D-C-A C-D-C-E C-D-C-F C-D-C-E C-D-C-G C-D-C-E C-D-C-F C-D-C-E C-D-C Quite a fun little finger exercise once you get your head around the pattern.

[@njf1410]

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.

[@davidjordan4598]

This is very interesting and engaging. Well done!

[@byoussef808]

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

[@guitarbrother1234]

The musical representation of the optimal solve was brilliant!

[@chrisweddle2577]

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.

[@mytube001]

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

[@DingbatToast]

Watching you solve it with musical notes was beautiful.

[@blackbear92201]

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

[@KhoaNguyen-sk7vv]

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 KZbin channels ever. I can't believe that this can happen!

[@adamreynolds3863]

that sounds incredible!

[@scotthamilton7131]

I like to imagine Ayliean has spent years determining optimal Tower of Hanoi solutions in this old brick room (perhaps in a tower itself) with its 1960's radiator and Christmas lights which have remained on since 2006. As soon as she solves a 50-disk problem, Eric Liddell himself comes and frees her.

[@Yotanido]

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.

[@BrianDiLoreto]

The audio representation of the optimal solution was amazing. Nice job on that and the animations Numberphile ! I would really love to hear the audio version of solutions for N > 6. If you produced an algorithm to generate these audio files, please share a few more solutions where N > 6. I think others would like that too.

[@CrystalStearOfTheCas]

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!

[@jannesvanquaillie9151]

this was great!!

[@callumroy8899]

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

[@barackobama5867]

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

[@chrisseddon5823]

Obama, still making the world a little better every day.

[@lukasmiller8531]

the classic!

[@XtecHubble]

lots of free time now..

[@chrisseddon5823]

@@XtecHubble Michelle would disagree.

[@samharkness8861]

That music sounded really good, thanks!

[@SOOKIE42069]

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

[@ZandarKoad]

Has someone done this? Can you link to it? Would love this as background music.

[@duytdl]

Always love it when Math + Music are combined.

[@marsgal42]

In a past job I did a lot of work with PostScript. One of my customer demos was the Towers of Hanoi: feed a PostScript file to the printer, it thinks for a second, then it prints a page with the moves on it.

[@xdata8122]

Mind-blowing ...that serpinski triangle and her enthusiasm!!!

[@webasdf]

I worked so hard in college to write a recursive function to solve this thing. I kept a printout of the program. I want to go find it now.

[@spencerkatty]

I've been obsessed with Sierpinski triangles since I was maybe 5 (Based on Legend of Zelda most likely), so I noticed her sweatshirt quickly into the video. The fact the patterns evolved into the triangle was amazing!

[@datboyace13]

This was too short 😫 lovely episode ❤

[@chrisv4312]

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.

[@BuShips]

Have you ever seen Close Encounters of the Third Kind?

[@JNCressey]

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.

[@briantw99]

It'd be very interesting to use notes from established chords, rather than just a scale. That way, you could play not just the note of the piece you moved, but the chord of it and the notes below it, but they'd always have a harmony, and then at the end you'd build up to the entire 6-note (or whatever number) chord.

[@jimneumann6099]

That was beautiful and inspiring ❤️😊