Key to the Tower of Hanoi - Numberphile
ฝัง
- เผยแพร่เมื่อ 16 ต.ค. 2024
- Featuring Ayliean MacDonald... Check out Brilliant (get 20% off their premium service): brilliant.org/... (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/MSRINumb...
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoun...
And support from Math For America - www.mathforame...
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Videos by Brady Haran
Additional sound design by Alan Stewart
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/...
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9
I think we might have a new “neatest brown paper” champion.
That handwriting, so amazing
For sure a podium place
Who is the old champion? Fedrico?
My thought, as well: A great video ("Serpinski Arrow" - cool!) with truly excellent handwriting
That is indeed very tidy brown paper
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!
I was trying to work out what the pattern would be for a 4 disc tower rather than the 3 used there.
klaatu barada nikto
@@telectronix1368 it’s a bigger Sierpinski triangle (4th iteration)
@@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
IKR Absolutely mindblowing
That was one of the best videos I’ve seen in a while. Love this hidden art in math stuff.
Cheers
Immediately clicked when mentioned how much the smallest piece moves.
??
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.
Not a hoodie. Sorry for being Hanoing.
* Scottish
I like how the fractal t-shirt was foreshadowing.
Same here.
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.
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.
That would make a great video
@@ancientswordrage Boy, do I have news for you.
Go look up 3b1b's video on the same topic
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...
Fun fact: this has an application on Super Mario 64 A button challenge
@@g.ricepad9470 Do tell.
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 :)
Do you have a link to an hour long (or long) Tower of Hanoi TH-cam music version?
First ever Tower of Hanoi video ever to not mention recursion! Also the most musical one...
In my opinion, not showing the recursive solution makes everything else pointless. The recursive solition is the very soul of the puzzle.
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?
It doesn't mention recursion directly but it is implied by the fact you get a fractal structure
@@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
In order to understand recursion, you must first understand recursion.
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
Plot twist: last note is a half note 😉
That was great - more from Ayliean please! Loved the secret jumper spoiler.
+
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!
Cool
Did you look at recursion or time complexity?
@@sub-vibes why is that?
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."
I have a presentation about this topic today
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!
Its probably the youtube algorithm buying info from your facebook or something. xp
I love it when patterns are easier to detect musically/rhythmically rather than visually.
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.
Nice one.
Yes, I did the same at work on a DEC PDP8 in 1967, but in assembler, using recursion.
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.
Uhm, Google knows where you are/
@@szkoclaw Sure, but Professor Layton on the DS doesn't :p
Never will I see this puzzle and not think of stacks of pancakes…
Which Layton Game it was?
@@pratyushkumarsahoo8591 Pandora's box if I'm not mistaken
Me 5 seconds into the video: Ooh cool jumper she's wearing
Me at 10 minutes into the video: HEY WAIT A MINUTE
This is so beautiful! Definitely one of my favorite videos from Numberphile!!
Thank you
This is the most amazing video on tower of hanoi!! OMG how crystal clear explanation!!!
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
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 :-)
Wow, I thought everyone in the world had drawn the state-space graph of the Hanoi towers!
She's great, hope to see more of Ayliean in the future.
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!
Wow. Thee music of that alone gave away the inevitability of the solution.
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.
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.
@@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
Omg best Numberphile yet, love your content Ayliean
Great episode! I love the "visualisation" using music. What is that called? Audiation?
Sonification :)
Notification ;-)
It’s called sonification or auralization.
Me seeing this video in my feed: Cmon it's a matter of odds and evens.
Me finishing this video: Mind blown.
This was so good! I hope we get to see Ayliean again. The jumper tie-in made me so happy haha
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!
12:52 Once you can hear it as 'hanoitonian' path, you cannot unhear.
This is fantastic. Tempted to go plug a few instances of this pattern into my sequencer and see what comes out of the synths...
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
3Blue1Brown already has a video on exactly this!
@@SpencerTwiddy Which one?
@@MrAlRats It's a 2-part video titled "Binary, Hanoi, and Sierpinski"
imo the best ever made on the subject
I never knew how to play this when I was young. I just thought it's supposed to be stacked randomly for fun
The philosophy in this quote is amazing!
Ah, to be young and carefree.
You know you've found a real mathematician when they stop to think about 64 minus 1. "Now, what number system are we using...?"
Actually, in all number systems 64 - 1 is still written 63
The value of the number depends on base, and we could be in any base above seximal
@@SpencerTwiddy Oh, if you only have to worry about *base*, sure... :)
@@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
I love how this made like 5 new connections about concepts I already knew.
The great thing about math is the number of connections that can be made. Its beauty comes from the complexity derived from perceived simplicity!
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!!!
Now I can compose music without any music lessons.
Thank you.
The moves also increase in a 2x+1 Pattern where x is the moves it take for the previous number of disks.
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
Ah dang, she pulled a sneaky one on us! I thought that was just a cool shirt!
I love arpeggios, and I gotta say that optimal solve slapped.
There weren’t any arpeggios in it but it did sound pretty🤪
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 !
Thanks
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.
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 :)
I had an exhibition and I'm in the maths club
Your video made me easy to do it
Thank u soo much❤❤❤
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.
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!)
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!
I love things that unexpectedly end up being the Sierpinski triangle.
WOW. From Hanoi tower to Serpinski triangle and Hamiltonian path. Mind-blowing.
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.
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.
Do you have a link to a lengthy musical rendition of this? Would love to listen while I'm working...
@@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.
Every time i come upon these in a video game from now on I'm gonna watch this video again 👍👍👍
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.
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.
That musical note thing was absolutely amazing.
It gives you goosebumps when she is unfolding Sierpiński triangle. Math is awesome
1:18 My brain kinda expected the music to go for 2 more notes
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 thoroughly enjoyed that. I had no idea where it was going at the start.
It's been a while since we last had a new face on Numberphile. Great video in every way!
Kudos to the editor for audio & video note work
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!
Hear for yourself at 1:42 - 1:45
Mathologer's video on the topic is highly recommended. It's called "The ultimate algorithm".
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.
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.
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 TH-cam channels ever. I can't believe that this can happen!
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.
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)
Three stages of me watching this clip
Phase 1: yes, yes, I know, 2^n-1, easily provable (if n rings require f(n) moves, additional n+1th ring requires moving n rings off, move n+1th, move n onto him back or f(n+1)=2*f(n)+1 which reduces to f(n)=2^n-1). Nothing new to see.
Phase 2: An easy algorithm? Just alternate moving the smallest in circles and the only other available move? Seriously? Wow, didn't know this. Great video.
Phase 3: Sierpinski? I am speechless. My mind is blown.
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 just sent this video to my Dad because he texted me complaining that he was playing Mass Effect and couldn't get past "the puzzle in Noveria".
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?).
That's a recursive solution in CS.
hanoi_solve(n) => hanoi_solve(n-1) + move_bottom + hanoi_solve(n-1)
hanoi_solve(0) => do_nothing
*flashbacks of the tower of Hanoi puzzle from the Noveria mission in Mass Effect 1*
Always love it when Math + Music are combined.
We programmed the problem in class a week ago, its really simple using recursion.
Obama, still making the world a little better every day.
the classic!
lots of free time now..
@@XtecHubble Michelle would disagree.
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.
Your hair is amazing, and it matches perfectly with your tower😍
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!
That music sounded really good, thanks!
I instantly recognized the optimal solve music as "The Ruler Song", a melody that my friends and I "discovered" in grade school while looking at (American) measuring sticks. Every inch was marked with a long line, every half-inch with a shorter line, every quarter-inch with an even shorter line, and so forth down to the sixteenths of an inch. To play The Ruler Song, simply "read" the ruler from left to right and play a note at each marking: the longer the line, the lower the note. So cool to hear the same tune again after all these years in a new mathematical context that's also related to the powers of two.
I would love to hear a version of that piece walking down the whole scale.
There is a simpler pattern. Using the original board with three spikes in a triangle. Starting with the tower on one spike. Give each block a number, starting with the top most block being '1' and numbering the blocks 2, 3, 4, 5, 6 and so on down the tower. The first move is block '1' to another spike. This is either a clockwise or anticlockwise direction. Which ever it is, it sets the moves for all the other blocks. If, for example you moved '1' in a clockwise direction, to the next spike, then all odd numbered blocks will move in a clockwise direction, from then on, when it is their turn to move and all even numbered blocks will move in an anticlockwise direction when it is their turn to move. Opening moves: '1' cw, '2' ccw, '1' cw (onto '2'), '3' cw, '1' cw, '2' ccw (onto '3'), '1' cw (onto '2' & '3'). '4' ccw', and so on.
Hm... so I can solve the 15-disk version in about three hours when I'm not concentrating on what I'm doing and just kinda going through the motions (mind, this is online, so tap and drag. It would obviously take me longer with an actual physical copy). That would put it at, what, about 180bpm, so roughly three clicks per second? Lol, I never really thought about that.
Funnily, I also never noticed that the disks follow a directional pattern with where each of them go. I kinda always just treated it as a recursive algorithm. If you have three disks, it's trivially easy to solve. If you have four disks, just solve the first three disks, then move the fourth one space over, and reassemble the first three disks on top. For five disks, do this, then move the fifth disk, and repeat to assemble the four-disk tower in the new position of the fifth disk, and so on.
The only pattern I ever really cared about was that the smallest disk has to go in whatever position you're *not* trying to assemble your tower in when there is an uneven number of disks in the tower you're working on (either the main tower for your first move or the sub tower you're currently working on to free up a new disk for moving), or it has to go in the place where you *are* trying to assemble the tower if there is an even number of disks in it. This rule has always really been all I needed to solve the towers in the optimal number of steps. That and recursion, of course 😅
Right, I made several tower of hanoi games in the past and you could simply pick one stack by pressing either 1, 2 or 3. Press one button to pick up the top disk from that stack and press another button drop it there. You can get incredible fast with just those 3 buttons ^^. Yes I also often use the recursive approach. Though at larger stacks you can easily get lost.
I also remember this odd / even rule. However you have it backwards ^^. If the number of disks is uneven (or odd) you have to move the first / top disk directly to the target position. Should make sense if you think about the smallest sub-tower which is just a single disk, so you move it where it should go. Whenever the number of disks is even you have to move the first disk to the other (temporary) stack. It's obvious when you think about a sub tower with 2 disks. Though kinda funny we essentially have the same approach.
@@Bunny99s It would be interesting to see how many approaches are out there. Apparently, the recursive one is a rather intuitive one that several people use. There's also the one from the video of course. Possibly other ones entirely?
The manual for the BBC Micro uses a Tower of Hanoi program to demonstrate recursive subroutines.
The musical representation of the optimal solve was brilliant!
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.
Have you ever seen Close Encounters of the Third Kind?
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.
So glad I didn't skip this one.
We’re glad too
Watching you solve it with musical notes was beautiful.
"Heh, that's a nice sweater. Good choice, even if it's unrelated!"
9:09
"Oh. Oh, I see."
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.
The Sierpinski triangle part is really interesting! I believe the optimal solution is unknown for 4 pegs, but maybe there's a similar pattern you could make using the same sort of diagram?
Edit: Apparently, the optimal solution is known for 4 pegs, but not 5 or more.
Took me a while to work it out, but I did get it eventually. Really cool to look at, I highly recommend giving it a go yourself. Also really cool how the last letter is consistent within a corner third of the triangle. Not surprising, but very interesting
hmm interesting, maybe the menger sponge has something to do with that
Apparently the "probably optimal" solution for the k-peg problem that's been knwon since 1941 was proven optimal for 4 pegs in 2014 and for k-pegs in 2016, but I don't confirm the correctness of either paper.
@@rmsgrey Oh, thanks for the information! I'll update my post.
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
Has someone done this? Can you link to it? Would love this as background music.
I learned most of this from experimentation, but learning its shape and mathematics was truly enlightening. Thanks for sharing!
the sonified result sounds a lot like the main theme of Michel Corrette's first concerto for organ!
Mind-blowing ...that serpinski triangle and her enthusiasm!!!
So I had figured out the solution to the Hanoi Tower puzzle on my own years ago, but the adding of musical notes was a beautiful twist to the process.
I live in Hanoi and somehow I don't even know this iconic game of ours existed before
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!