@@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
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.
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...
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.
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.
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 :)
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?
@@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
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 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
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."
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!
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 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!
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
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.
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!
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.
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
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
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!
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 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.
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.
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!)
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.
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)
@@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
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.
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 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.
I only knew, that there is a definite start and a definite end. With that, the oddity of the number of discs is important. When the positions are A, B and C, where A is start and C is the end, then the rules of optimal solving goes like this: When the number of discs is even (2, 4, 6, ...) then disc 1 goes A -> B -> C. When the number of discs is odd (1, 3, 5, ...) then disc 1 goes A -> C -> B. Disc 1 has the first move and takes every second move. On the other turns (an empty position is seen like a very big disc), the smaller disc goes to the bigger disc.
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.
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?).
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!!!
Ayliean, if you put the imaginary poles into an imaginary triangle, then it will be much more obvious that the littlest peice is going around in a 'circle', so to speak, and more obvious that the different pieces are moving clockwise vs counter-clockwise. (That melody was surprisingly lovely, btw!)
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.
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.
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 !
Back in the days this had been a task in data processing class. We had to design a computer program which had to assign the next move to the player. No one in the class had ever heard of recursion. After three weeks the teacher looked at the results. I wrote approximately 2000 fully packed lines of "C" code but the program failed in the end. Most of my classmates didn't spent that much effort in that. The teacher then revealed the solution to us with a three line "C" code program and told us about computing tasks which only can be solved by recursive algorithms. I will always remember this story.😁
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
Another way of solving this is to realise that to move a tower that's bigger than 1 disc to a position is to move a tower that's 1 smaller to the other position, then move the biggest disc and then move the smaller tower on top of that. To move that smaller tower you use the same method. When it's just 1 disc you you just move that. This is the way you could solve it with a recursive function in a computer program. What you also find out this way is that if you want to move an odd number of discs you start at the position where you want to end up and with an even number you start at the other position.
The pattern i figured out when i was younger was by looking at the portion of the tower you want to move, determine if the number of rings is odd or even, and decide where the target location of that portion is. If the number is odd, you place the top piece on the target location; even, and its on the non-target location. Take the 3 piece tower. Odd number, you want to put it on the right side. Top piece goes to the right. What remains is even, so the next piece goes to the middle. The next piece you want to move is the top piece, and your target is on the second piece. Now you can move the third piece, which standing alone, is an odd number. Move it to the right. The remaining portion in middle is even, so piece goes away from target, second piece is odd, goes on the right side, then cap it off. Its a completely repeatable pattern for any number of rings. If you had even number of rings to start, you'd just move the first piece to the center.
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.
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.
Did I guess there was a Sierpiński triangle in there somewhere from her top? Maybe, maybe not... What a lovely video this is! Nothing quite like hidden mathematical elegance.
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.
this is the fundamental principle behind some sorting algorithms. when you're constrained by memory space and you can't just distribute everything into everywhere and pick it back together, you do this: move, take the thing you want, move back and free the space for the next thing. a similar trick is used in card magic: you put the card you want up or down the deck, then cut, and the card is now at the opposite end.
![[102] How to solve the Towers of Hanoi](/img/n.gif)
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
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
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.
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.
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 😉
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.
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
Wow. Thee music of that alone gave away the inevitability of the solution.
I love it when patterns are easier to detect musically/rhythmically rather than visually.
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
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
The moves also increase in a 2x+1 Pattern where x is the moves it take for the previous number of disks.
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
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!
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 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 had an exhibition and I'm in the maths club
Your video made me easy to do it
Thank u soo much❤❤❤
12:52 Once you can hear it as 'hanoitonian' path, you cannot unhear.
I love arpeggios, and I gotta say that optimal solve slapped.
There weren’t any arpeggios in it but it did sound pretty🤪
This is the most amazing video on tower of hanoi!! OMG how crystal clear explanation!!!
She's great, hope to see more of Ayliean in the future.
WOW. From Hanoi tower to Serpinski triangle and Hamiltonian path. Mind-blowing.
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
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.
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
This is so beautiful! Definitely one of my favorite videos from Numberphile!!
Thank you
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.
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
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
This is fantastic. Tempted to go plug a few instances of this pattern into my sequencer and see what comes out of the synths...
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!
Me seeing this video in my feed: Cmon it's a matter of odds and evens.
Me finishing this video: Mind blown.
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.
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!
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.
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!
It gives you goosebumps when she is unfolding Sierpiński triangle. Math is awesome
Now I can compose music without any music lessons.
Thank you.
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.
Me 5 seconds into the video: Ooh cool jumper she's wearing
Me at 10 minutes into the video: HEY WAIT A MINUTE
That musical note thing was absolutely amazing.
This was so good! I hope we get to see Ayliean again. The jumper tie-in made me so happy haha
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.
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.
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!)
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.
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.
Mathologer's video on the topic is highly recommended. It's called "The ultimate algorithm".
I love things that unexpectedly end up being the Sierpinski triangle.
Every time i come upon these in a video game from now on I'm gonna watch this video again 👍👍👍
Ah dang, she pulled a sneaky one on us! I thought that was just a cool shirt!
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)
Great episode! I love the "visualisation" using music. What is that called? Audiation?
Sonification :)
Notification ;-)
It’s called sonification or auralization.
Omg best Numberphile yet, love your content Ayliean
*flashbacks of the tower of Hanoi puzzle from the Noveria mission in Mass Effect 1*
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.
Kudos to the editor for audio & video note work
I thoroughly enjoyed that. I had no idea where it was going at the start.
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.
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
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.
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.
I only knew, that there is a definite start and a definite end.
With that, the oddity of the number of discs is important. When the positions are A, B and C, where A is start and C is the end, then the rules of optimal solving goes like this:
When the number of discs is even (2, 4, 6, ...) then disc 1 goes A -> B -> C. When the number of discs is odd (1, 3, 5, ...) then disc 1 goes A -> C -> B.
Disc 1 has the first move and takes every second move.
On the other turns (an empty position is seen like a very big disc), the smaller disc goes to the bigger disc.
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.
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
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!!!
Ayliean, if you put the imaginary poles into an imaginary triangle, then it will be much more obvious that the littlest peice is going around in a 'circle', so to speak, and more obvious that the different pieces are moving clockwise vs counter-clockwise.
(That melody was surprisingly lovely, btw!)
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.
I live in Hanoi and somehow I don't even know this iconic game of ours existed before
The musical representation of the optimal solve was brilliant!
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.
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
Back in the days this had been a task in data processing class. We had to design a computer program which had to assign the next move to the player. No one in the class had ever heard of recursion. After three weeks the teacher looked at the results. I wrote approximately 2000 fully packed lines of "C" code but the program failed in the end. Most of my classmates didn't spent that much effort in that. The teacher then revealed the solution to us with a three line "C" code program and told us about computing tasks which only can be solved by recursive algorithms. I will always remember this story.😁
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.
Always love it when Math + Music are combined.
That music sounded really good, thanks!
I would love to hear a version of that piece walking down the whole scale.
Another way of solving this is to realise that to move a tower that's bigger than 1 disc to a position is to move a tower that's 1 smaller to the other position, then move the biggest disc and then move the smaller tower on top of that. To move that smaller tower you use the same method. When it's just 1 disc you you just move that.
This is the way you could solve it with a recursive function in a computer program.
What you also find out this way is that if you want to move an odd number of discs you start at the position where you want to end up and with an even number you start at the other position.
So glad I didn't skip this one.
We’re glad too
Watching you solve it with musical notes was beautiful.
Mind-blowing ...that serpinski triangle and her enthusiasm!!!
The pattern i figured out when i was younger was by looking at the portion of the tower you want to move, determine if the number of rings is odd or even, and decide where the target location of that portion is. If the number is odd, you place the top piece on the target location; even, and its on the non-target location.
Take the 3 piece tower. Odd number, you want to put it on the right side. Top piece goes to the right. What remains is even, so the next piece goes to the middle. The next piece you want to move is the top piece, and your target is on the second piece. Now you can move the third piece, which standing alone, is an odd number. Move it to the right. The remaining portion in middle is even, so piece goes away from target, second piece is odd, goes on the right side, then cap it off.
Its a completely repeatable pattern for any number of rings. If you had even number of rings to start, you'd just move the first piece to the center.
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.
The music is a massive giveaway. A trained musician can follow it without looking and instantly understand what's going on.
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?
Did I guess there was a Sierpiński triangle in there somewhere from her top? Maybe, maybe not... What a lovely video this is! Nothing quite like hidden mathematical elegance.
This is the Hanoi Radio and Television Station!
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.
That's a really nice way to see the solution to the puzzle.
Also, I think the music from the shortest solution path makes a musical Palindrome.
It's been a while since we last had a new face on Numberphile. Great video in every way!
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.
1:18 My brain kinda expected the music to go for 2 more notes
this is the fundamental principle behind some sorting algorithms.
when you're constrained by memory space and you can't just distribute everything into everywhere and pick it back together, you do this: move, take the thing you want, move back and free the space for the next thing.
a similar trick is used in card magic: you put the card you want up or down the deck, then cut, and the card is now at the opposite end.
Been following her on tiktok for a while. Never thought I’d see her on numberphile!