"If you're ever captured by an evil toymaker, you'll be ready" And they say math has no real-world applications.

That's it, I'm stealing that. I'm no longer a Software Engineer, I'm an Algorithmologist.

17:40 "This recipe also solves another Hanoish puzzle." I think the correct adjective is "Hannoying".

40 minutes of Professor Polster + links to 400 hours of reading = 1 helluva education Every single time, thank you for all you're doing, Mathologer!

Don't let other KZfaqrs doing the same topics stop you. Please! I like to see different takes on the same topic from my favorite KZfaqrs.

There must be millions of people who have heard of the Tower of Hanoi puzzle and the simple algorithm that generates the simplest solution. But what happens when you are playing the game not with three pegs, as in the original puzzle, but with 4, 5, 6 etc. pegs? Hardly anybody seems to know that there are also really really beautiful solutions which are believed to be optimal but whose optimality has only been proved for four pegs. Even less people know that you can boil down all these optimal solutions into simple no-brainer recipes that allow you to effortless execute these solutions from scratch. Clearly a job for the Mathologer. Enjoy :)

The best thing about Reve's puzzle; "We're going to have some cheese."

23:33 there’s another lovely pattern that’s easy to miss in this table; look at the antidiagonals. See anything familiar?

13:27 In 1,023 moves, moving the smallest disc every other move means we're moving it 512 times, which is 2 (mod 3). So we need to move it counter-clockwise (A -> C -> B -> A) to make sure it ends at B. In general, 2^(n-1) is 1 (mod 3) if n is odd and 2 (mod 3) if n is even, so we should move the smallest disc clockwise if n is odd and counter-clockwise if n is even.

After checking a feel cases, I think that to get the tower from A to B, you start by moving the smallest disc to: • C, if there are 2n discs; • B, if there are 2n+1 discs.

If the tower has an odd number of discs, first move the smallest to the place you want the tower to end up. If even, move to the space you don't want the tower to end. Then just consistently follow the direction you moved the smaller disc to (clockwise/counterclockwise if arranged as a triangle, to the left/right with wraparound if arranged in a line).

So happy to see a new video. I was really upset when you didn't upload in February.

The toy maker himself wouldn't expect this video to come out one day during that time

In 1983 I got a Commodore 64 for my 8th birthday. My dad got some 5-1/4" floppy disks full of public domain BASIC games and one of them was Tower of Hanoi. That was the last time I heard of Tower of Hanoi. 🙂

These are some of your most visually satisfying animations to date, which is really saying something!

Increbile, the amount of astractions one's mind can demarcate around a given subject. Just wow, maths is beautiful

The Toymaker is Hanoi'ing me again.

I checked your channel three times this week, I was expecting this, LET'S GOOOOO

I figured out best solution for tower of hanoi when i was 6... My dad gave to me tower of hanoi puzzle with 8 peaces and so that i don't bother him said that i should find best solution and left me like that, and then was very surprised that 3 hours later i came to him and said "255", he already even forgot that he gave me the puzzle, but back in those days i figured out the recursive solution to tower of hanoi which impressed my father quite a bit... I was always good with recursive algorithms...

For n disks, the shorthand trick I remember is that odd heights start by moving the small disk to the destination peg and even starts by moving it to the intermediate peg.

Bioware put this in KotOR, and I had to memorize this thankfully simple recipe because I did multiple playthroughs. Years later, they put it in Mass Effect 1 and I still remembered it. And years later I saw this video and still remembered it. Stuff you do repeatedly as a kid really sticks with you, huh?

I used to solve towers of hanoi on fights because I had no internet. Solving the 10-peg version with 1023 moves must've been one of the proudest moments in my life :D Edit: huh, I didn't know the "smallest disk" trick explained at 12:18. I just tried to follow the recursive algorithm in my head. Way to trivialize my life's achievment, Mathologer! /s

I have seen a lot of comments before saying that they needed the video before, but I didn't expect this one to be one of those. This was the topic of my research paper for my gifted class last year, specifically the smallest amount of moves to win a k-poled Hanoi Tower, and I plan to carry on this year. I haven't finished the video, but thank you for this wonderful video anyway. Cheers from Korea! Edit: Never thought about 4-peg Hanoi Towers with the concept of superdisks. Thanks again.

31:05 I believe I read, was mentioned in one of my Logic classes, or ???: For every Provable True Theorem, there are an infinite number of True Unprovable theorems. "There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy.".

I remember watching 3B1B's video on Hanoi and feeling such awe, that a seemingly simple puzzle could weave recursion and binary counting together. I never thought anything could replicate that awe again! But damn you! Thank you soo much for making me experience that awe again, and this time much muchh more! I just can't wait to get on my computer and try to animate all the animations that you showed today (and perhaps even a generalised version for small n using Frame-Stewart algorithm?). But seriously lot's of love and respect man for making me fall in love with Maths over and over again!

2nd problem is 3^n because there are n discs, each of which has 3 'choices' of pegs - same as the number of vertices on the sierpinski triangle 3rd problem can be done by comparing coefficients of 12/59 and 18sqrt(17)/1003, upon which irrational parts drop out - not sure I want to do this.. -btw, thanks Mathologer!

The trick I always used for the tower of Hanoi is based on odd or even quantity of discs. If you have an odd number of discs then the first move will be to the target tower. If you have an even number, then your first move will be to the other empty tower.

As others have shared, I also really enjoy Mathologer's take on these great topics even if other math channels I follow like 3B1B cover them! Every minute spent on this production by the team was worth its weight in gold (or cheese disks) I always get this sense like it's Christmas morning when I see a new video from you guys, thanks for pumping up my weekend!

for the record, T. Bousch also has a strong contender in the "best title for a math paper, ever" category : Le Poisson n'a pas d'arête (Annales de l'Institut Henri Poincaré, 1999)

Oh, what could be nicer than a weekend with a mathologer video :)

Sir can I say, despite the time, your videos are ABSOLUTELY AMAZING! KEEP UP THE GOOD WORK! :)

This kind of single move algorithms often show up in computer science and an often overlooked follow up question is if their were "multithreading" where if two subsequent movements occurred to and from different pegs they could be done simultaneously as 1 move. Obviously this would only apply to larger n but I would be curious if the solutions for that were actually superior given how ordered the solutions seem to be already.

Me every time a Mathologer video comes out: *visible excitement*

Yes mathologer video when i'm bored is the best of the best

Excellent video, I love the visuals & extending the tower of hanoi puzzle beyond what's typically talked about

Easily one of the best channels on all of youtube. Thank you once again for a very interesting, entertaining, learnful, and inspiring video, professor Burkard! 🙌

I love the little giggles. Could be a bady in a bond movie

0:56 that puzzle becomes really hard really quick if allow to input not only number disks but sticks as well.

Once time again a Wonderful Video from Mathologer !!! Thank you.

Let's gooooooooooooooooooooooooo! :D

"Oh , I know about this puzzle" "how tf I never thought about multiple pegs"

I think, because of how common the Tower puzzle is, and how little I've thought about it before, this is one of the most beautiful videos you've done. Despite many years of studying more complex topics, making "simple" problems elegant often gives me the greatest appreciation of mathematics. Thank you as always!

For those who don't know: the reason you only saw a still and heard an audio is that only photos from the TV broadcast and a duplicate audio of the telecast are what BBC have in the archives of the first three episodes. Addendum: there was a proposed sequel to "The Celestial Toymaker" called "Nightmare Fair". Rumour had it that an early draft of the script included the Doctor solving the minimal path problem discussed here for the Trilogic game.

Decided to implement in python before watching. An interesting point I came across was that when recursing, the midpoint and destination swap for subtower move (so the biggest disc can move to the destination unimpeded). As the algorithm recurses down to the base case of 1 (not 0), there are n-1 such midpoint/destination swaps for a tower of size n. Hence, for towers with an odd number of discs, there are an even number of mid/dst swaps, which all cancel out -> first move should be the first disc on to the intended overall destination. Vice versa for even number of discs.

So happy to see the video for this month. Wish they were more times then once a month, but am sure it takes a long time to make these, and happy that you make them

Couldn’t be happier to see this video and try the challenges!

I remember finding formula for the smallest number of moves required for n disks and an algorithm to solve it, when I were 12 years old. Those were great times.

Your videos are mind-ticklers! Thank you

13:50 if n is odd: clockwise if n is even: counter-clockwise or another way to phrase it: if n is odd: first move is to the target position if n is even: first move is to the OTHER position

Every one of your videos is so amazing, Professor Burkard. Best on the internets

•Always loving your videos. 🥰🥰🥰 Love from India 🇮🇳🇮🇳🇮🇳. •By the way, if you plug in 3 for n, you get 《946/243》(=3.893) •Please make videos on ☆☆☆ Unsolved problems in Mathematics ☆☆☆.

beautifuly done as always. I have enjoyed every part of this video. thanx!

#1: Nine disks need forty-one (41) moves. My solution is the "minimum of (two times a smaller number of disks plus the minimum of the remaining disk moves) method. #2: An observation: if d (# of disks) < p (# of pegs), then you ALWAYS only need 2*d-1 moves. Basically, having more pegs than disks means you can move every disk to its own peg, including the base disk (to the designated ending peg), then move all of the other disks back on to the next bigger disk, which you should have already moved to that ending peg: (d - 1) + 1 + (d - 1) = 2d - 1. #3: Likewise, if d = p, then m = 2d + 1, since you will have to move whichever disk is on the ending peg (or move another disk, if the ending peg is the only one available to the biggest disk), move the biggie, move the disk you had to move beforehand, and then move all the other disks onto the biggie: (d - 1) + 1(clear off the ending peg) + 1(biggie) + 1(split the double stack up with the starting peg) + (d - 1) = 2d + 1.

Wonderful video. Thank you for making these!

One of your best videos, thanks!

Already smashed the like button multiple times before Intro was finished. Such was the enthusiasm to learn.

What a fantastic video again! Thank you very much!

I didn't even notice that the movie and tv references were gone, nice to see a revival!

Brilliant and very satisfying video!

My interest in maths came back after my exam .

Such a great explanation! Excellent!!!

Perfect, my friend! Thanks!

Todos tus videos son espectaculares. Gracias por tomarte el trabajo de hacerlos, son realmente inspiradores.

Beautiful visualizations!

Funny and awesome, as always! I've enjoyed it. I'll think about the puzzle with for and five pegs!

There was no Easter egg at the end, but I always watch the entire (always wonderful) video(s). Thank you, Mathologer!

Amazing!!! Enjoy your storytelling style to explain the mathematical concepts and algorithms.

Always so curious to see vedios , thanks a lot mythologer , love from Nepal

I find myself revisiting your hugely helpful references again. Kudos to Team Mathologer!

14:00 For odd number of disks, move clockwise; for even, move counter-clockwise. Easy to see. if one disk (or odd), move directly to ending peg; otherwise, not.

I'm so glad to see (literally) that your color scheme became more colorblind-friendly!

Thank you for this excellent video. It was worth watching.

Love Your Mind, My Friend,,, Keep up the Incredible Work; You have a #1 Fan Here!!!

I am ready for the tomaker now! Thankyou Mr Mathologer

15:52 I love the Michael Ende quote

Thank you for another excellent video.

Incredible explanation!

It's often used to teach recursion. And last semester our professor used Fibonacci sequence and towers of Hanoi as two examples to show different programming languages. Including postscript, which was quite fascinating

Your videos are so interesting and inspiring

Another Gem From Mathologer. Hats Off !

I distinctly remember seeing this on our steam driven television the first time round... by then I’d graduated from watching from behind the sofa (for safety reasons...), it had a big impact on me ... I made a version of the game at school and started a craze for playing it that lasted two whole weeks! Nerd heaven.....

While I never faced it, I was considering the programming interview question: "Solve the Tower of Hanoi puzzle using a recursive function." Here's my problem with this interview question: It doesn't actually *need* a recursive function. I'm of the opinion that if you can craft more supportable code, however less "elegant," it is, you will be doing right by your client. Here's how I would structure it (using English rules for pseudocode): Assume N disks (Labeled Disk 1 through Disk N) Assume 3 rods (Labeled 1, 2, and 3) Assume all disks are first placed on Rod 1. All moves follow the rules (The only disk that can ever be moved to either rod is Disk 1. All other exposed disks can only move to the rod not occupied by Disk 1.) Rule 0: (One time move) 　If N is even, move Disk 1 to Rod 2; 　　Else, move Disk 1 to Rod 3. LOOP ((N^2)-2)/2 times: 　Step 1: 　　Move the smallest disk that is not Disk 1. 　Step 2: 　　If Disk 1 is not on Disk 2, move Disk 1 to Disk 2; 　　　Else, 　　　If the two non-1 disks are both even or both odd 　　　　Move Disk 1 to cover the larger disk 　　　　Else, 　　　　Move Disk 1 to cover the even disk That's it. One single one-time move, and a loop that bounces back and forth between a non-decisive move, and a 3-option decision move. I believe this approach would be easier to read and maintain by someone who came along later. "Elegance" is great if it saves time, and is clear and easy to maintain. But it doesn't have client value in and of itself.

14:43, this wicked sense of humor had me in stitches.

The puzzle at 16:35 is the one the Celestial Toymaker should use if he wants to hanoi you.

You left out the fact that the Hanoi constant 466/885 gives the average distance between any two points in a sirpinski triangle with a side length 1

13:27 The doctor has to move the tip counter-clockwise because B in that picture corresponds to the lower right corner of the triangle we had looked at before. In general, if you have a tower with n disks, you have to move the tip clockwise for odd n and counter-clockwise for even n for the tower to end up at B (according to this picture). Moving a tower with an even number of disks to B means that you first move a tower with one less disk and thus an odd number of disks to C and since a single-disk tower can be moved with one move only, the tip of a tower with an odd number of disks moves initially to the place where the whole tower will eventually end up. Therefore, if the tower has an even number of disks, the tip has to move to a different place than the final location.

I just recently found a code golf where the challenge was to quine that output a unique program every iteration, without repeat, for however many iterations. I immediately thought of Gray code, and have been absorbed. This is great!

Thanks for the video!! Greetings from Brazil :)))

By the way, Dr. Who was a great show! Great choice for introducing the Tower of Hanoi puzzle!

havent watch it yet, but its a gift to watch your videos.

I had the Tower of Hanoi on my graphing calculator way back in middle school, and used to 'speedrun' 10 disc solutions when I was bored in math class, so I can actually say with relatively high confidence I could still pull it off without a mistake. There's a nice rhythm to it once you get the hang of it, almost meditative. Interestingly, because it was presented as a straight line of pegs instead of a triangle of them, I never stumbled on the clockwise/counterclockwise solution to figuring out where the top disc goes, another example of how how you frame a problem affects how you solve it. Instead, my method was to think in terms of a start peg, a storage peg, a goal peg, and partial pyramids. Move the top part of the pyramid to one peg (the target peg if the pyramid has odd number of discs, the storage peg if it has an even number), move the top disc of the bottom part of the pyramid to the other peg, move the top part of the pyramid on top of it, and now you have a bigger top part and a smaller top part. Repeat until there's just one disc on the start peg, move it to the other peg, and then you have a new whole pyramid, and you recurse back to the start, just with the start and the storage peg switched places, and a pyramid one disc shorter.

Tower of Hanoi is a super popular interview question, so much so that I bet interviewers have to tweak the question so it's new to interviewees. I imagine asking about more pegs is a frequent extension. Now I feel prepared. Great vid

Mathologer: *Explains mathematical induction in under a minute* Teachers: *take notes furiously*

18:16 (shortest solution with extra adjacent-peg rule): it is obvious that we have to visit all the nodes in the graph, and a path traversing x nodes exactly once requires x-1 arcs. So, the question boils down to evaluate the number of nodes in such a graph, that is essentially composed by all the possible valid configurations of disks on pegs. With 1 disk we have 3 valid configurations (the smallest triangle), with 2 disks we have 9 valid configurations (the 2nd-smallest triangle), with 3 disks we have 27 valid configurations (...), etc. Note that when we assign a "set" of disks to a peg, their placement is uniquely determined (since it must comply the no-big-over-small rule) by the total ordering of disk sizes. Then, the total number of configurations is the number of ways to assign n disks to 3 pegs; that is the question "with n available digits, how many numbers can I build that are 3-digits long" and the answer is 3^n. Having 2^n nodes in the graph, having to traverse all of them exactly once, the shortest "adjacent-peg" solution is of length 3^n-1 with 3 pegs; more generally with p pegs the shortest "adjacent-peg" solution is of length p^n-1 by the same reasoning.

For the second problem, recursion is T(n) = 3T(n-1) +2 as largest disc moves twice and the n-1 disc pile has to be moved from one extreme to another thrice. Solving the recursion gives the promised beautiful answer - 3^n-1

Video uploaded 1 minute ago and already had 5 likes. I am really impressed by the amazing mind power of mathologer's viewers where they fast forwarded a 40 minute video to watch in 1 minute and still understood it well to like the video at the end. Or may be they used some kind of algorithm i am mot sure. Great job guys!

I just can't stop watching these videos

Very nice , keep sharing such knowledge at KZfaq platform :)

I suddenly have an urge to program an animation for something like 35 discs moving using 6 pegs, just so I can sit back and watch 35 discs moving using 6 pegs. This is the reason I like math - it can be very beautiful sometimes... ------------ Update: (I'm going to keep updating this as I discover new things until I'm done with my programming, at which point I'll post the program here) While trying to make this whole thing more algorithmic, I discovered another way to find the next move of a Tower of Hanoi puzzle of 3 pegs given ONLY the state of the puzzle (so none of that "every second move, move the smallest disc" stuff allowed): Say your state is ABBAC (as in disc 5 is on A, disc 4 is on B, disc 3 is on B, disc 2 is on A, and disc 1 is on C) and your ultimate goal is to move disk 5 to peg C. Now, change each of these letters to a number in the following way: for odd-numbered discs, change A --> 0, B --> 2, and C --> 1 (mod 3) as our goal will now be to move disc 5 from 0 to 1. For even numbered discs, change A --> 0, B --> 1, and C --> 2 (basically swap the roles of B and C). This changes ABBAC to 01201. Now follow the following procedure: M5 (the number of times we moved disc 5, mod 3) equals 0, since it started on peg 0 and ended on peg 0 (no change). Q5 is defined as "whether or not we moved disk 5", and can be 0 or 1. With the largest disc, this is easy; Q5 = M5 = 0. Now define M4 as the number of times we moved disc 4 (mod 3 - from now on we're working in mod 3), which is going to be 1 (the second digit in 01201 - this is actually the reason I defined this convoluted procedure of converting letters to numbers, so that we could easily see this correlation). At this point, let's quickly talk about something else. Notice that the order in which we move each of the discs (seen in the animations of 3-peg Hanoi in the video) is an ABACABADABA pattern (or rather, a 121312141213121 pattern). We will use this to our advantage; let's say we chop the string of moves 1213121412131215121312141213121 - which is the solution for 5-disc 3-peg Hanoi - somewhere in the middle, like here: 121312141213121512131 / 2141213121 Note that the number of 4s before the split is always going to be the number of 5s, and possibly one more. Similarly, M3 (going with the notation used earlier) is always M4 + M5 + [either 0 or 1]; M2 = M3 + M4 + M5 + [either 0 or 1], etc. Redefine Q_n to be this [either 0 or 1] value for disc n - note that this doesn't change the value of Q5 - and continue working as follows: M4 = 1 = M5 + Q4 = 0 + Q4 ∴ Q4 = 1 M3 = 2 = M5 + M4 + Q3 = 0 + 1 + Q3 ∴ Q3 = 1 M2 = 0 = M5 + M4 + M3 + Q2 = 0 + 1 + 2 + Q2 ∴ Q2 = 0 (remember, mod 3...) M1 = 1 = M5 + M4 + M3 + M2 + Q1 = 0 + 1 + 2 + 0 + Q1 ∴ Q1 = 1 Remember, these Mn values are coming from the string of numbers we found earlier (01201). Now organize these Q values from smallest to largest disc: 10110 Pick the first 0 you find (left to right), which in this case is Q2, which corresponds to disc 2. Move the disc you chose from A-->C-->B if odd (since this is the direction in which we want disc 5 to move), and move the disc from A-->B-->C if even. This means the next move of the puzzle is to move disc 2 from A to B. ...and that's it! Whew, quite long, don't you think? I'm still surprised it's even possible, so I'm not going to complain though... Time to implement this into my code!

30:07 Minimum number of moves for 9 disk and 4 pegs (I think): 41 (^.^). You explained how to divide the disks into 3 superdisks for 8 disks but not for 9. So, just for fun, I tried every possible division in a very inefficient c++ code. I found that you can solve optimally in 41 moves if you divide the disks into 3 superdisks of 2, 3 and 4 disks (from top to down); also dividing them into 4 superdisks of 1, 1, 3 and 4; 1, 2, 2 and 4; AND 1, 2, 3 and 3. I didn't check if these divisions provide different solutions (Challenge for anybody?), but my guess is that, at least, the 3 and 4 superdisk divisions are different optimal solutions. Calculation (hopefully) explained: Assume that you got to solve for 8 disks and 4 pegs, and you divide the 8 disks into 3 superdisks of 1, 3 and 4 disks (from top to down, like Mathologer did). Also note that f(n)=2^n-1 is the optimal number of moves to solve n disks and 3 pegs. Then, (hopefully) it's easy to see that the number of moves, following the Mathologer path, is equal to f(1)+f(3)+f(1)+f(4)+f(1)+f(3)+f(1)=4f(1)+2f(3)+f(4)=2^2 f(1)+2^1 f(3)+2^0 f(4). Note that the arguments of the f's add up to the 8 disks and also note the decreasing powers of 2. (hopefully) it's easy to see that, for n disks, 4 pegs and m superdisks of a1, a2, ..., am disks, such that a1+a2+...+am=n, the resulting number of moves is equal to 2^(m-1)f(a1)+2^(m-2)f(a2)+...+2^0 f(am). For the code, I simply apply this formula to every possible division of the 9 disks into superdisks. I cycle through the possible divisions in a very inefficient and lazy way: I go though all possible lists of between 1 and 9 elements with all possible values between 1 and 9, checking if the accumulation of the elements add up to 9. Seeing the formula, it's easy to see that it's not worth it to check superdisk divisions that are not in decreasing amounts of disks, but whatever. Here's the code for anyone interested: #include #include #include //accumulate algorithm using namespace std; int pow(int b,int e){//b to the power of e with e being a non negative integer int ans=1; for(int i=0;i