I am seriously surprised to see someone bring the Hanoi tower problem, positional notation and space-filling curves in a >30min explanation. Now I'm even more convinced that every two areas in mathematics are related in some interesting way.
It is imperative field. Of course they are related if the only way to construct an plausible hypothesis is to satisfy criteria which are imperative for every other piece of math.
@@ЭльмирЭльмир-д5с is that a rigourous term, "imperitive field" I feel like it all comes down northers theorem a lot of the time. Like most he manually found an isomorphisms to modular set. But further, it was so clean because it identified with operations per base. So he really made a much more fundamental connection to counting. Idk but there's almost always an invariant which implies and is implied by a symetry.
+ΣΚΡΟΥΤΖ ΜΑΚ ΝΤΑΚ I guess, there might be a shorter solution than counting quaterny... Imo the most efficient structure is something like "solve 3-restricted towers of Hanoi for the first n-1 layers, move n once, bring the top tower back, move n twice, solve 4-restricted towers of Hanoi for the first n-1 layers" Hereby, 3-restricted means restricted and 3 pillars. However, for small numbers of disks, there are even shorter solutions: with only disks 0, 1 and 2 we get 0+0+0+1+1+2+1-1-2+0-0-2+0+1+0-0-1+1+0+0+0+ or better, where n+ is a movement of disk n to the right and n- is a movement of disk n to the left. In quaterny we could code this (in another way than in the video, i.e. absolute positions instead of movements) as 000, 001, 002, 003, 013, 023, 123, 113, 103, 203, 202, 201, 301, 302, 312, 311, 310, 320, 330, 331, 332, 333
Pascal's triangle has some very interesting properties. It also encodes pi, it encodes e, it contains all natural powers of two in it's rows and all simplex numbers (triangular, tetrahedral, pentatope and so on...) in adjacent diagonals.
I've heard that it also contains the Fibonacci numbers, which are linked to the golden ratio. My question is: does it also contains the integer sequences linked to the silver ratio, bronze ratio and higher such metallic numbers?
I thought it couldn't get much better than Essence of Linear Algebra. I may have been wrong. This is fabulous - it's mind-blowing, beautiful, and elegant. I love how you relate recursion to counting, then to a famous problem, and then finally to graphs. To a math-CS enthusiast like me, this is stuff of dreams!
What I find amazing about the ToH inscribed within Sierpinski"s Triangle is that if you start a tone corner and follow the Towers of Hanoi along any given edge, it will actually show you the most efficient solution to solving the ToH associated with that triangle. Truly mind boggling.
Woahh.. this mapping between counting, base 3, towers of Hanoi and Sierpinski's triangle is truly beautiful, and your knack for animations truly does the material respect, every time. I'm proud to be finally supporting you on Patreon.
Dude, I feel like this channel is about to blow right up. I almost guarantee than in 6 months you'll have at the minimum 100k subscribers. I love this content and animations, I'm looking very much forward to the exponential growth of subs :D
Sorry pal but you were wrong ...He already has 100k after 2 weeks! xd. And he got another 4 thousand in the last 2 days. "Blowing up" is the right description. Btw, how did you see the future?
Lol, a little luck and experience- I've seen lots of these really high quality channels like this get popular really fast. It almost happens over night. It always seems to start slow - for months and months a heap of contents, and then all of a sudden, BAM! Subs out the ying yang. I so all that just gave me a feeling that this about to happen to this channel.
Kevin Octacok Well, I guess as long as this channel has less subscribers than any other math channel out there on youtube he should have more to be fair.
Man I follow your channel since the beginning. I love your stuff! Thank you! Your number of viewers is going to explode, no doubt. Oh and yes you are right desmos is dope! Thanks again!
I love your videos because either I start making the leaps in logic myself and I feel like a genius for deducting it before you tell it or I have ZERO idea and my mind gets absolutely blow
Theemathas Chirananthavat bit and byte sound like our slang word for penis, and bool sounds like our slang word for testicles. dunno if its okay to write them on RUclips?
Well, you've gotten your revenge. A research tool that I use a lot is called Coq. National animal of France and all that. Coincidence? Of course :). It's an endless source of amazing jokes.
Fascinating and brilliantly explained! The only thing to add is that each vertex is a solution to the Hanoi Tower and hence following an edge will get you from one to the other.
*Goes through comments, finds several thanking the creator of the beautiful work of art that is this video, streak gets broken by firsts and seconds* ahh the internet
Great work as always! I admire the way you're replacing "hand waving" with intuition that makes sense, and on that, I have a note - the thing that was most unclear to me during watching the video, was this - the Sierpinski Triangle is only seen in this way if we know where to place each node on the plane. But if I were to do it from scratch, how would I know where to place the nodes before I draw the edges? There is some unexplained magic to it, and even though I figured out by myself the other things which were unclear to me (which are only a few, as a sign you're doing it well), and I believe you share with me this idea - both mathematicians and magicians love magic tricks, but while a magician never reveals his secrets, a mathematician always will. So, I guess my question, where did this rabbit come from? Kindly awaiting your response.
Great question. Phenomenal question, in fact, since I had to grapple with while coding these animations. It's actually a neat recursive puzzle for anyone out there who wants to think about it. (The key is to flip triangles appropriately while recursively generating Sierpinski's triangle).
I had the same question when I was whatching. I imagine that, even not knowing the Sierpinski triangle shape, if you do it from scratch on a paper or something like that, you would find the shape when you organize the nodes to the edges doesn't cross each other.
How I would search for a graphical solution for this is by throwing down all the nodes as points in the plane, connecting the ones that are connected, and trying to group them together. Then, it's whatever fancy arrangement you prefer. Of course, if you do that, you'll see what connections there are, and I think at that point trying to group them like in the video would come naturally, just by making all connections have equal length. In general, there is no one good way in graph theory to present a graph. There are cases like this where the graph is so regular that it looks best in a triangle/triforce-like shape, but there are others where that still isn't very good-looking. For example graphs that are bound to be self-intersecting in 2D (everything 4 points and up with every connection drawn for example).
Honestly don't understand why this does NOT have more views at the time of writing this. Beautiful explanation and just blew my mind. Hope you and Vsauce keep up the good work! Appreciate it!
about 8:50 I got nerd chills. Fractals are self-similar and the self-similarity of a counting in a certain base can be connected to a fractal. Maybe another base in the Hanoi puzzle gives the Sierpinski carpet?? What a great channel!
10:38 - "Isn't that crazy?!" Just then you reminded me of Brady. "There's this _amazing_ thing, and you don't know it, but you _have_ to know it!" Inspiring awe, one video at a time. :)
You mean Brady Haran? I can totally imagine him saying that: "There's this amazing thing that you don't know, but you have to know it. Isn't that crazy?!?!"
I hate to say this and I hope I'm wrong, but I think there is no deeper pattern in the numbers that each node translates to. I looked at a few different sizes and didn't find one. However, there is some (obvious, if you know it) pattern. You just need a different assignment from node to number. Let's say in each node, the position of disc n (where left position = 0, middle = 1, right = 2) signals the number in the 3^n spot (aka (n-1)th spot counted from behind) . Easier than it might sound. So [-][1,0][2] -> 211, as disc 2 is in position 2 (right) and disc 1 and 0 are in position 1 (middle). and for example [1][2,0][-] -> 101 If you're now going through all nodes with the given path, you end up with this sequence: oeis.org/A128173 The Gray Code is a code, where two successive values differ in only one trit (in base 3). This is however not that surprising if you consider the fact that between two nodes there is only one move allowed, so only one disc shifts, so with the new assignment only one trit changes.
That's what I thought about too... It's also a really cool connection to the Hausdorff dimension of the Sierpinsky triangle, since the bottom row contains 2^n different states, the whole "area" of the triangle 3^n.
Also, each corner represents a complete tower in one of the pegs A, B or C and the edges of the triangles represent the unconstrained solutions to move the tower from one of those pegs to another. I wonder what the structure would look like for 4 or more pegs.
Wonderful! These videos are amazing. I could have watched this in high school and still understood what you said in these two videos. Seeing these connections really reminds me of why I enjoyed math in the first place.
Fun tip, you can traverse other Sierpinski fractals with other base counting as well. You can also represent it in musical notation pretty easily since we often count in binary and ternary in western music (which are primes and used to divide larger time signatures anyway).
These videos are absolutely brilliant. And mind blowing. Space filling is crazy enough- still trying to wrap my mind around mapping one dimension to two (I often think of the fact that a photon's energy is just a single dimensioned wavelength, yet we can perceive in three dimensions). Hard to believe you can create a curve that in its limit space fills a fractal. How could a single dimensioned function map to such a complex structure? The mind boggles...
For a french person who study binary, bits are funny the five first minutes. The real problem is to explain what it is to someone not used to this term. But I can remember some laughs during my lessons... (A bit, sounds like "bite" in french, which are slangs for male genitalia...). By the way, "bite" in English, doesn't sounds like "bite" in French, but writing it the first few time, feels really weird... Good video ! Already knew the trick, but fun to watch =)
I really wanted you to throw in just a single line as you constructed Sierpinski about how you are just taking successive Cartesian Products of the graphs. The idea of Cartesian and Kronecker products are really cool and important when you get to visualizing graph structure.
3:35 I'm french, and bits is quite a popular term, so we don't find this term too off. But tbh, most of us don't even know that bits stand for binary digits.
If binary digits are bits, and ternary digits are trits , these are the other base systems' digit names up to base 16: bits, trits, quadrits, quintits, sextits, septits, octits, nonits, digits, hendigits, dozenits, tridigits, quadridigits, quintidigits and sextidigits .
Great stuff, just reading about it I really did not get the connection between Towers of Hanoi and the Sierpinski triangle, but as usual your explanation and animation flawlessly conveys the information even to a mathematical dud like me :)
3Blue1Brown, these two are probably my favorite videos by you. That's just fascinating. Thank you, sir. I'll also say that as a high school Calculus student, we use Desmos a lot, and while I absolutely love their graphing calculator, the lessons meant for our class have generally been confusing. I specifically recall one on the Mean Value Theorem that involved playing with tangent/secant lines for a while and then the program asking us if on a continuous smooth graph they could always be parallel. As this was my first introduction to the concept and I'm not the best at abstraction, I had no idea. And that was how it ended; I'm not even sure it directly told us what the MVT was. I can say that the rest of the class was as confused as I was though. Oh well, just me complaining. They could be fantastic in other areas.
I think you shoud have mentioned that, to solve the unconstrained hanoi towers problem using the Sierpinski Triangle, in the most efficient manner, you can just go along one of the edges of the triangle. I noticed that while watching the vídeo and thought it was beautiful, because the binary number counting system, used do solve this problem, can be seen in the path from a vertice to the given state in the solution, in the oposite edge. Let's say I want to solve the problem, going through the bottom edge, every state in this path connects to the top vertice by a single path with no horizontal lines, and in that path the binary number associated with the state is coded in the left or right turns in the top node of each triforce pattern. Hope you can see what I mean, it's amazing how a problem like this can be solved with such an intuitive vizualization.
A tower with 4 pins instead of 3 won't be "solved counting" in base 4, but it should exist at least one game than could be "solved counting" in base 4 ( and N), a relative graph and a relative filling courve. I'll try to work on it, but I'm not sure I have all the knowledge to manage it. Thanks for all your great videos, you are always a source of inspiration
I got a question, what happens if we add a "D" peg onto the Hanoi tower puzzle? does the sierpinski triangle shifts into a square? And if that happens, so does the counting process? Awesome video, you're literally opening my mind in every topic yout touch and develop. Keep it up! :3
A 4th peg allows solutions with fewer moves. In the unrestricted case it destroys the pattern of moves required for the most efficient solution. Multiple solutions exist for 4 or more disks.
3B1Br, your videos are excellent for people such as myself who have studied a modest amount of college or graduate-level mathematics. I think you have a knack for explaining high-level concepts from multiple angles, and in simple(est?) terms. I am curious whether you've ever considered working on material geared more towards high school students, but in this style.
Omg, this is such a beautiful set of interconnected ideas ! By the way the trail looks like an eulerian path, which makes the sierpenski graph/fractal more interesting :)
For your constrained tower of Hanoi problem, the state graph is actually just a line. That is, at any given state, there are exactly two legal moves, except for "entire tower on A" and "entire tower on B" which have only one legal move each. This is pretty easy to prove, and guarantees that the problem is solvable! I found that surprising. Starting at "entire tower on A," if you continue making legal moves without backtracking, the only outcome is that you go on forever (impossible), you come back to a previously visited state (impossible), or you eventually reach "entire tower on C." I'd love a simple explanation for why you traverse every state along the way, i.e. why the state graph doesn't have a disconnected loop. Is this obvious?
That would represent a fractal of a shape with 2 sides. You can count all of the Sierpinski N-gon fractals using Base-N counting, so Base-2 would be a 2-gon fractal (I.E. an ever expanding line segment). Not sure what other problems or games like the Tower of Hanoi that can be modeled with the other bases though. Might need Game Theory for to connect the dots on that one.
Nice video. :-) This video would've been GREAT when I was in my algorithms class when we had to solve this exact problem on our own. Lol. The towers of hanoi problem is no issue, but the constrained version gives a lot of students a lot of trouble. There were a lot of variations that we faced though. The professor likes to deal with all kinds of hanoi graphs. The one you showed here can be represented by the graph, A B C Legal moves are A to B, B to A, etc. But not A to C for example. Some that we had to deal with were like, A -> B -> C -> A ->... It's cyclic in a single direction. Another one was like, A -> B -> C -> D -> B ->... That one is cyclic in a single direction, but only after peg A. So you have to unload all the pegs off of A, and you can never return to peg A. They're cool to think about, but pretty harsh to assign to students learning algorithms for the first time in a sort of sink or swim environment. You explained it WAAAAY better than the professor ever did though. Lol. Oh well, I got through that class pretty well. I'm graduating in December.
I would love to see you put out little videos that are just beautiful visual animations of some concept like this, leaving the explanation for another time.
Elliott Collins That's effectively possible now if you mute the video and put on whatever music you'd like. Re-watch with an explanation at your convenience.
You also get quite a nice pattern if you take the Sierpinski triangle graph, and colour the edges according to which disc is being moved at that edge. It lets you see how common the small disc ones are in the middle, vs. how rare the largest disc is at just three around the very outside.
One of the first ways I learned about constructing fractals was via Lindenmayer systems, so I guess I was pre-biased to already think of a Sierpinski triangle as a curvy thing! There are a zillion ways to define a Sierpinski triangle as the limit of an L-system; here's one of my favorites: Axiom: A Rules: A → B-A-B B → A+B+A For those unfamiliar, the way L-systems work is: Start with the axiom, let's call it s0. To get s1, go through your rules and replace every instance of a symbol with whatever's on the right-hand side of its rule. So in the example above, s0 is the string A, and s1 is the string B-A-B. Then we get s2 by doing the same thing with s1. s2, then, is A+B+A-B-A-B+A+B+A, and so forth. This gets out of hand pretty quickly doing it manually, but with a computer it's easy to expand this string as far as you want or have room in memory. Then what you're left with is basically a *set of instructions* to one of those LOGO turtles you may have encountered if you've ever taken an intro CS class. A or B move the turtle forward a step, drawing a line as it goes; + turns it clockwise (by 30 degrees here), and - turns it counterclockwise. The further out you go, the better approximation you get of a Sierpinski triangle! You can draw all sorts of fractals this way. The way to do replacements, and the way to interpret the resulting string when drawing, can get more sophisticated than that, but that's the basic idea.
This reminds me of an introductory question from my problem solving math class 1 1/2 years ago: to create a function outputting the number of odd numbers in a given row of Pascal's triangle. Apparently when labeling the rows of Pascal's triangle in binary, with row 0 being the single 1 on top, the number of odd numbers in any row is 2^(number of odd digits in the binary row number).
Two possibilities, both with a similar compliment to Keith Schwarz. Either: a.) he was working from a script, in which case his reading of the script comes off marvelously casual and I compliment his presentation. or b.) he was not working from a script, in which case he is a marvelous communicator and educator and I compliment his presentation.
Not sure if anyone has commented on this before, but the solution you are describing is for the problem "Move all disks from A to C", not for the problem "Move all disks from A to some other place". Otherwise it would be possible to move n disks from A to B by a) moving n-1 disks from A to C (using the method described in the video) b) moving the nth disk from A to B c) moving n-1 disks from C to B (similar to the whole problem, so use recursion) For four disks, this means only 40 moves are needed instead of 80.
the fact that sierpinski triangle graphs always have a way to navigate can be framed in usual terms of graph theory: reframe the graph with connections and nodes swapped, and you have a graph where every node is connected to exactly two other nodes, and all of them are connected.
The binary number in the beginning was not synchronized with the placement of the tower things, since it stated at 1 and not at 0. For example the 0-plate moved while the second digit changed at the first time :)
Beautiful explanation. Also, I think we can use base n for The Towers of Hanoi puzzle if we use n pegs, and constraint ourselves to move the disc to adjacent places. So, if we took 10 pegs and the discs can move only to adjacent places in the puzzle, we should count in decimal system. Correct me if I'm wrong.
This is absolutely beautiful, thank you so much for appreciating this to the degree where you take the time to do these awesome animations! I now know of 3 very separate ways of constructing the Sierpinski triangle: Geometric rules (triangle, subdivide to 4 triangles, remove middle piece; iterate) Chaos game (3 edges, a die; 1&2 correspond to edge 1, 3&4 to edge 2, 5&6 to edge 3; iterate (throw die) thousands of time from a random starting point; remove the first 50-100 steps) The towers of Hanoi, as showed in this video. Anyone know of any other way to produce this fractal?
started with a CS assignment to write a recursive solve for Hanoi and now I'm on here counting fractals... I think maybe this is the first video I've actually understood (I'm not very smart).
If you arrange the three pegs in a triangle rather than a line and view them from above, the sierpinski graph feels slightly less surprising in that the direction of each graph edge can be made to line up with the direction of the associated disk move.
Ah, the bottom row and the long sides describe the most efficient way in the non-constraint puzzle. And this constraint puzzle is a 2d-version of it. If we need to go deeper, we need one more "solution" (as in the corners are solutions to a whole problem). Therefore this Sierpinski triangle in 3d would need one more pole. And 5-pole-game could be described with a super Sierpinski tetrahedron.
At 9:15 you show part of the graph, but you said that it was the constrained version of the puzzle, and the movement that you showed would be ilegal in the constrained version. I love all your videos btw, just something that i noticed, if you could explain me what it is or if it is a mistake, doesnt matter, your content is wonderful, hugs from Brazil
The following problem which I came across recently is also related to this video: _A merchant had a forty pound measuring weight that broke into four pieces as the result of a fall_. _When the pieces were subsequently weighed, it was found that the weight of each piece was a whole number of pounds and that the four pieces could be used to weigh every integral weight between 1 and 40 pounds_. _What were the weights of the pieces?_ "Apparently it was first posed by Claude Gaspard Bachet de Méziriac in a book of arithmetic problems published in 1612, and can also be found in Heinrich Dorrie’s _100 Great Problems of Elementary Mathematics_."
I am seriously surprised to see someone bring the Hanoi tower problem, positional notation and space-filling curves in a >30min explanation. Now I'm even more convinced that every two areas in mathematics are related in some interesting way.
*
It is imperative field. Of course they are related if the only way to construct an plausible hypothesis is to satisfy criteria which are imperative for every other piece of math.
@@ЭльмирЭльмир-д5с is that a rigourous term, "imperitive field"
I feel like it all comes down northers theorem a lot of the time.
Like most he manually found an isomorphisms to modular set. But further, it was so clean because it identified with operations per base. So he really made a much more fundamental connection to counting.
Idk but there's almost always an invariant which implies and is implied by a symetry.
Well, it's actually 30 means more than 30 and since this video is 13 minutes then the correct one is
@@zahidulhaque1757 I think they were counting both parts, but still I think it doesn't even total half an hour.
Trits? What about a base four digit? I'd call it quits...
This should be top comment xD
I wondered what shape we'd get if we had the constricted Hanoi problem with 4 sticks. I think I'll just quit now :P
Base 6 gives me the shits.
farts
+ΣΚΡΟΥΤΖ ΜΑΚ ΝΤΑΚ I guess, there might be a shorter solution than counting quaterny...
Imo the most efficient structure is something like "solve 3-restricted towers of Hanoi for the first n-1 layers, move n once, bring the top tower back, move n twice, solve 4-restricted towers of Hanoi for the first n-1 layers"
Hereby, 3-restricted means restricted and 3 pillars.
However, for small numbers of disks, there are even shorter solutions:
with only disks 0, 1 and 2 we get
0+0+0+1+1+2+1-1-2+0-0-2+0+1+0-0-1+1+0+0+0+ or better, where n+ is a movement of disk n to the right and n- is a movement of disk n to the left.
In quaterny we could code this (in another way than in the video, i.e. absolute positions instead of movements) as
000, 001, 002, 003, 013, 023, 123, 113, 103, 203, 202, 201, 301, 302, 312, 311, 310, 320, 330, 331, 332, 333
Fun fact: You can also make a Sierpinski triangle by highlighting the odd numbers of Pascal's triangle.
Pascal's triangle has some very interesting properties. It also encodes pi, it encodes e, it contains all natural powers of two in it's rows and all simplex numbers (triangular, tetrahedral, pentatope and so on...) in adjacent diagonals.
Wat?
I've heard that it also contains the Fibonacci numbers, which are linked to the golden ratio. My question is: does it also contains the integer sequences linked to the silver ratio, bronze ratio and higher such metallic numbers?
@@MuzikBike the what
Even more fun, try colouring Pascal's Triangle according to mod 3 or mod 5. You get some neat patterns!
I thought it couldn't get much better than Essence of Linear Algebra. I may have been wrong.
This is fabulous - it's mind-blowing, beautiful, and elegant. I love how you relate recursion to counting, then to a famous problem, and then finally to graphs. To a math-CS enthusiast like me, this is stuff of dreams!
What I find amazing about the ToH inscribed within Sierpinski"s Triangle is that if you start a tone corner and follow the Towers of Hanoi along any given edge, it will actually show you the most efficient solution to solving the ToH associated with that triangle. Truly mind boggling.
Woahh.. this mapping between counting, base 3, towers of Hanoi and Sierpinski's triangle is truly beautiful, and your knack for animations truly does the material respect, every time. I'm proud to be finally supporting you on Patreon.
+
There is more.
U can use a list of binomial coefficients to solve a random valid configuration. :)
Dude, I feel like this channel is about to blow right up. I almost guarantee than in 6 months you'll have at the minimum 100k subscribers. I love this content and animations, I'm looking very much forward to the exponential growth of subs :D
Sorry pal but you were wrong ...He already has 100k after 2 weeks! xd. And he got another 4 thousand in the last 2 days. "Blowing up" is the right description.
Btw, how did you see the future?
Lol, a little luck and experience- I've seen lots of these really high quality channels like this get popular really fast. It almost happens over night. It always seems to start slow - for months and months a heap of contents, and then all of a sudden, BAM! Subs out the ying yang.
I so all that just gave me a feeling that this about to happen to this channel.
Kevin Octacok
Well, I guess as long as this channel has less subscribers than any other math channel out there on youtube he should have more to be fair.
What's so astonishing to me is that concepts like this one (well, all mathematical concepts) have always been there and we're just uncovering them.
This thanksgiving I'm thankful for 3Blue1Brown... Your "essence of linear algebra" series resonated the most with me. Keep it up man!
It's so insane how everything in math is so connected.
Of course... it's the language that God used to create the universe!
I'm wondering why there are people don't like these series, I thought it is amazing and the animations are elegant!
Thanks!
Why on earth would you ask a French speaker for advice about numbers? I can think of at least four-twenty-ten-nine reasons not to
I got four-twenty-ten-nine problems but a sensible number system ain't one
It's not about the numbers but because In French Bits mean "Dicks"
@@42Seke it's bites not bits
@@Anna-jy7cj they are two different things
ne pensez même pas à critiquer notre langue. Nous aussi on va le faire
Man I follow your channel since the beginning. I love your stuff! Thank you! Your number of viewers is going to explode, no doubt. Oh and yes you are right desmos is dope! Thanks again!
I love your videos because either I start making the leaps in logic myself and I feel like a genius for deducting it before you tell it
or I have ZERO idea and my mind gets absolutely blow
I'm a french IT engineer and have heard jokes about bits, bytes and bools all my life. Okay, I've also told a lot of them.
Maxime Euzière What do those words mean in French?
Theemathas Chirananthavat bit and byte sound like our slang word for penis, and bool sounds like our slang word for testicles. dunno if its okay to write them on RUclips?
Well... if it's purely for educational reasons...
bytes sound like "bite" = dick
and bools like "boules" = balls
Well, you've gotten your revenge. A research tool that I use a lot is called Coq. National animal of France and all that. Coincidence? Of course :). It's an endless source of amazing jokes.
Fascinating and brilliantly explained!
The only thing to add is that each vertex is a solution to the Hanoi Tower and hence following an edge will get you from one to the other.
I'd like to nominate every single of your videos for the "WHOAAA DUDE" Steam-Award. You are awesome!
I don't care what anyone else thinks, this is hands down the coolest channel on RUclips
I'm studying math education in college right now and your videos are absolutely wonderful! You've got the skills I want to have.
*Goes through comments, finds several thanking the creator of the beautiful work of art that is this video, streak gets broken by firsts and seconds* ahh the internet
I have watched this video before, but now that i am studying CS, i really appreciate the beauty of it. Thanks Grant Sir.
Amazing work, as usual! These two videos just made my day!
Great work as always! I admire the way you're replacing "hand waving" with intuition that makes sense, and on that, I have a note - the thing that was most unclear to me during watching the video, was this - the Sierpinski Triangle is only seen in this way if we know where to place each node on the plane. But if I were to do it from scratch, how would I know where to place the nodes before I draw the edges?
There is some unexplained magic to it, and even though I figured out by myself the other things which were unclear to me (which are only a few, as a sign you're doing it well), and I believe you share with me this idea - both mathematicians and magicians love magic tricks, but while a magician never reveals his secrets, a mathematician always will.
So, I guess my question, where did this rabbit come from?
Kindly awaiting your response.
Great question. Phenomenal question, in fact, since I had to grapple with while coding these animations. It's actually a neat recursive puzzle for anyone out there who wants to think about it. (The key is to flip triangles appropriately while recursively generating Sierpinski's triangle).
I had the same question when I was whatching. I imagine that, even not knowing the Sierpinski triangle shape, if you do it from scratch on a paper or something like that, you would find the shape when you organize the nodes to the edges doesn't cross each other.
How I would search for a graphical solution for this is by throwing down all the nodes as points in the plane, connecting the ones that are connected, and trying to group them together. Then, it's whatever fancy arrangement you prefer. Of course, if you do that, you'll see what connections there are, and I think at that point trying to group them like in the video would come naturally, just by making all connections have equal length.
In general, there is no one good way in graph theory to present a graph. There are cases like this where the graph is so regular that it looks best in a triangle/triforce-like shape, but there are others where that still isn't very good-looking. For example graphs that are bound to be self-intersecting in 2D (everything 4 points and up with every connection drawn for example).
Honestly don't understand why this does NOT have more views at the time of writing this.
Beautiful explanation and just blew my mind. Hope you and Vsauce keep up the good work!
Appreciate it!
This channel has filled the void that Vihart has left in my life
about 8:50 I got nerd chills. Fractals are self-similar and the self-similarity of a counting in a certain base can be connected to a fractal. Maybe another base in the Hanoi puzzle gives the Sierpinski carpet?? What a great channel!
Wonderful topic and animations Sir, I hope you never stop doing these masterpieces.
10:38 - "Isn't that crazy?!"
Just then you reminded me of Brady. "There's this _amazing_ thing, and you don't know it, but you _have_ to know it!"
Inspiring awe, one video at a time. :)
You mean Brady Haran? I can totally imagine him saying that: "There's this amazing thing that you don't know, but you have to know it. Isn't that crazy?!?!"
Mind blown! What a great piece of work. Congratulations, one of the best pieces of educational video. Ever.
Is the bottom row of the triangle the most efficient way to solve the Hanoi puzzle if it was unconstrained?
Yes! Isn't that awesome?
Interestingly in ternary numbers they read: 000, 002, 010, 011, 211, 212, 220, 222. The pattern? I haven't found it yet but I'm sure there is one!
I hate to say this and I hope I'm wrong, but I think there is no deeper pattern in the numbers that each node translates to. I looked at a few different sizes and didn't find one.
However, there is some (obvious, if you know it) pattern. You just need a different assignment from node to number.
Let's say in each node, the position of disc n (where left position = 0, middle = 1, right = 2) signals the number in the 3^n spot (aka (n-1)th spot counted from behind) . Easier than it might sound.
So [-][1,0][2] -> 211, as disc 2 is in position 2 (right) and disc 1 and 0 are in position 1 (middle).
and for example [1][2,0][-] -> 101
If you're now going through all nodes with the given path, you end up with this sequence: oeis.org/A128173
The Gray Code is a code, where two successive values differ in only one trit (in base 3).
This is however not that surprising if you consider the fact that between two nodes there is only one move allowed, so only one disc shifts, so with the new assignment only one trit changes.
That's what I thought about too... It's also a really cool connection to the Hausdorff dimension of the Sierpinsky triangle, since the bottom row contains 2^n different states, the whole "area" of the triangle 3^n.
Also, each corner represents a complete tower in one of the pegs A, B or C and the edges of the triangles represent the unconstrained solutions to move the tower from one of those pegs to another.
I wonder what the structure would look like for 4 or more pegs.
Wonderful! These videos are amazing. I could have watched this in high school and still understood what you said in these two videos. Seeing these connections really reminds me of why I enjoyed math in the first place.
Fun tip, you can traverse other Sierpinski fractals with other base counting as well. You can also represent it in musical notation pretty easily since we often count in binary and ternary in western music (which are primes and used to divide larger time signatures anyway).
This was a really good complement to the binary trees video made by Vihart some years ago. Loved it, as always
Truly excellent. The constrained solution is even more beautiful that the free one.
These videos are absolutely brilliant. And mind blowing. Space filling is crazy enough- still trying to wrap my mind around mapping one dimension to two (I often think of the fact that a photon's energy is just a single dimensioned wavelength, yet we can perceive in three dimensions). Hard to believe you can create a curve that in its limit space fills a fractal. How could a single dimensioned function map to such a complex structure? The mind boggles...
A great couple of videos! Coming from someone who doesn't understand all your videos.
For a french person who study binary, bits are funny the five first minutes. The real problem is to explain what it is to someone not used to this term. But I can remember some laughs during my lessons... (A bit, sounds like "bite" in french, which are slangs for male genitalia...). By the way, "bite" in English, doesn't sounds like "bite" in French, but writing it the first few time, feels really weird...
Good video ! Already knew the trick, but fun to watch =)
I really wanted you to throw in just a single line as you constructed Sierpinski about how you are just taking successive Cartesian Products of the graphs.
The idea of Cartesian and Kronecker products are really cool and important when you get to visualizing graph structure.
In French "bite" pronounced "bit" is an appendage, such as a bollard or a hook, but is most often used to described the male appendage
3:35 I'm french, and bits is quite a popular term, so we don't find this term too off. But tbh, most of us don't even know that bits stand for binary digits.
If binary digits are bits, and ternary digits are trits , these are the other base systems' digit names up to base 16: bits, trits, quadrits, quintits, sextits, septits, octits, nonits, digits, hendigits, dozenits, tridigits, quadridigits, quintidigits and sextidigits .
I'm pretty sure some of those are serious afflictions
Eh, closest would probably be 'dozenits' as 'dozenitis' would be inflammation of the twelve.
Base 12 would probably be dodigits,
+
I propose to switch to a base 6 counting system as a way to boost interest in maths
Great stuff, just reading about it I really did not get the connection between Towers of Hanoi and the Sierpinski triangle, but as usual your explanation and animation flawlessly conveys the information even to a mathematical dud like me :)
3Blue1Brown, these two are probably my favorite videos by you. That's just fascinating. Thank you, sir.
I'll also say that as a high school Calculus student, we use Desmos a lot, and while I absolutely love their graphing calculator, the lessons meant for our class have generally been confusing. I specifically recall one on the Mean Value Theorem that involved playing with tangent/secant lines for a while and then the program asking us if on a continuous smooth graph they could always be parallel. As this was my first introduction to the concept and I'm not the best at abstraction, I had no idea. And that was how it ended; I'm not even sure it directly told us what the MVT was. I can say that the rest of the class was as confused as I was though.
Oh well, just me complaining. They could be fantastic in other areas.
I think you shoud have mentioned that, to solve the unconstrained hanoi towers problem using the Sierpinski Triangle, in the most efficient manner, you can just go along one of the edges of the triangle. I noticed that while watching the vídeo and thought it was beautiful, because the binary number counting system, used do solve this problem, can be seen in the path from a vertice to the given state in the solution, in the oposite edge. Let's say I want to solve the problem, going through the bottom edge, every state in this path connects to the top vertice by a single path with no horizontal lines, and in that path the binary number associated with the state is coded in the left or right turns in the top node of each triforce pattern. Hope you can see what I mean, it's amazing how a problem like this can be solved with such an intuitive vizualization.
this video blew my mind completly. Great job!
this channel always give high-quality videos for edu. Recommended👍
These videos never fail to amuse me
you have explained very nice.visualisatio is simply superb. Its really useful for me. and I m waiting for more useful videos like these from u.
When you finish your escence of calculus series, an "Escence of Group Theory" series would be amazing (if you are into that kind of stuff).
A tower with 4 pins instead of 3 won't be "solved counting" in base 4, but it should exist at least one game than could be "solved counting" in base 4 ( and N), a relative graph and a relative filling courve. I'll try to work on it, but I'm not sure I have all the knowledge to manage it. Thanks for all your great videos, you are always a source of inspiration
Love your work by the way!
I got a question, what happens if we add a "D" peg onto the Hanoi tower puzzle? does the sierpinski triangle shifts into a square? And if that happens, so does the counting process?
Awesome video, you're literally opening my mind in every topic yout touch and develop. Keep it up! :3
I think more pegs would either make the process shorter or not actually affect it at all.
A 4th peg allows solutions with fewer moves. In the unrestricted case it destroys the pattern of moves required for the most efficient solution. Multiple solutions exist for 4 or more disks.
"...literally opening up my mind..." That's an... interesting choice of words there. ( ͡° ͜ʖ ͡°)
It would shift into a tetrahedron.
If you tried converting this shape into 2D, you would get this: www.exocortex.org/toh/toh-4-4-main.gif
mathsboy314 cool. so thats how you make a Sierpinski tetrahedron
3B1Br, your videos are excellent for people such as myself who have studied a modest amount of college or graduate-level mathematics. I think you have a knack for explaining high-level concepts from multiple angles, and in simple(est?) terms. I am curious whether you've ever considered working on material geared more towards high school students, but in this style.
Omg, this is such a beautiful set of interconnected ideas !
By the way the trail looks like an eulerian path, which makes the sierpenski graph/fractal more interesting :)
This is seriously the coolest thing ever!! Thank you for making this video!
Great video as always, thanks for all the great work you put into these :D
This is spectacular! I wish I had found this channel sooner!
one of the best videos I've seen in a long time, thanks!
For your constrained tower of Hanoi problem, the state graph is actually just a line. That is, at any given state, there are exactly two legal moves, except for "entire tower on A" and "entire tower on B" which have only one legal move each. This is pretty easy to prove, and guarantees that the problem is solvable! I found that surprising.
Starting at "entire tower on A," if you continue making legal moves without backtracking, the only outcome is that you go on forever (impossible), you come back to a previously visited state (impossible), or you eventually reach "entire tower on C." I'd love a simple explanation for why you traverse every state along the way, i.e. why the state graph doesn't have a disconnected loop. Is this obvious?
That would represent a fractal of a shape with 2 sides.
You can count all of the Sierpinski N-gon fractals using Base-N counting, so Base-2 would be a 2-gon fractal (I.E. an ever expanding line segment).
Not sure what other problems or games like the Tower of Hanoi that can be modeled with the other bases though. Might need Game Theory for to connect the dots on that one.
Incredible video, as always. Astonishing beauty.
I'm so grateful for this video.
The same recursion reveals itself in many ways!
Shouldn't it be called Terts?
Bi-nary digi-ts
Ter-nary digi-ts
b-its
so it should be called tits
teri-nary, terits
Tits
Tetrary - Tetris
What about "tigits"? Bits, tigits, quidgits, quintits, sextits...uh oh...
Nice video. :-) This video would've been GREAT when I was in my algorithms class when we had to solve this exact problem on our own. Lol. The towers of hanoi problem is no issue, but the constrained version gives a lot of students a lot of trouble.
There were a lot of variations that we faced though. The professor likes to deal with all kinds of hanoi graphs.
The one you showed here can be represented by the graph,
A B C
Legal moves are A to B, B to A, etc. But not A to C for example.
Some that we had to deal with were like,
A -> B -> C -> A ->...
It's cyclic in a single direction.
Another one was like,
A -> B -> C -> D -> B ->...
That one is cyclic in a single direction, but only after peg A. So you have to unload all the pegs off of A, and you can never return to peg A.
They're cool to think about, but pretty harsh to assign to students learning algorithms for the first time in a sort of sink or swim environment. You explained it WAAAAY better than the professor ever did though. Lol. Oh well, I got through that class pretty well. I'm graduating in December.
Really nice video, easy to understand with pictures! Thank you so much
I would love to see you put out little videos that are just beautiful visual animations of some concept like this, leaving the explanation for another time.
Elliott Collins That's effectively possible now if you mute the video and put on whatever music you'd like. Re-watch with an explanation at your convenience.
You also get quite a nice pattern if you take the Sierpinski triangle graph, and colour the edges according to which disc is being moved at that edge. It lets you see how common the small disc ones are in the middle, vs. how rare the largest disc is at just three around the very outside.
One of the first ways I learned about constructing fractals was via Lindenmayer systems, so I guess I was pre-biased to already think of a Sierpinski triangle as a curvy thing!
There are a zillion ways to define a Sierpinski triangle as the limit of an L-system; here's one of my favorites:
Axiom: A
Rules:
A → B-A-B
B → A+B+A
For those unfamiliar, the way L-systems work is: Start with the axiom, let's call it s0. To get s1, go through your rules and replace every instance of a symbol with whatever's on the right-hand side of its rule. So in the example above, s0 is the string A, and s1 is the string B-A-B. Then we get s2 by doing the same thing with s1.
s2, then, is A+B+A-B-A-B+A+B+A, and so forth. This gets out of hand pretty quickly doing it manually, but with a computer it's easy to expand this string as far as you want or have room in memory. Then what you're left with is basically a *set of instructions* to one of those LOGO turtles you may have encountered if you've ever taken an intro CS class. A or B move the turtle forward a step, drawing a line as it goes; + turns it clockwise (by 30 degrees here), and - turns it counterclockwise. The further out you go, the better approximation you get of a Sierpinski triangle!
You can draw all sorts of fractals this way. The way to do replacements, and the way to interpret the resulting string when drawing, can get more sophisticated than that, but that's the basic idea.
This reminds me of an introductory question from my problem solving math class 1 1/2 years ago: to create a function outputting the number of odd numbers in a given row of Pascal's triangle. Apparently when labeling the rows of Pascal's triangle in binary, with row 0 being the single 1 on top, the number of odd numbers in any row is 2^(number of odd digits in the binary row number).
That is really beautiful :) Thank you for yet another awesome video!
Two possibilities, both with a similar compliment to Keith Schwarz. Either:
a.) he was working from a script, in which case his reading of the script comes off marvelously casual and I compliment his presentation.
or
b.) he was not working from a script, in which case he is a marvelous communicator and educator and I compliment his presentation.
Kyle Goryl Excluded middle FTW!
The conversation with Keith was not scripted, he's just a genuinely great communicator.
Not sure if anyone has commented on this before, but the solution you are describing is for the problem "Move all disks from A to C", not for the problem "Move all disks from A to some other place". Otherwise it would be possible to move n disks from A to B by
a) moving n-1 disks from A to C (using the method described in the video)
b) moving the nth disk from A to B
c) moving n-1 disks from C to B (similar to the whole problem, so use recursion)
For four disks, this means only 40 moves are needed instead of 80.
superb content ! as usual ........great channel
the fact that sierpinski triangle graphs always have a way to navigate can be framed in usual terms of graph theory: reframe the graph with connections and nodes swapped, and you have a graph where every node is connected to exactly two other nodes, and all of them are connected.
this is so beautiful, thank you for sharing this!!
The binary number in the beginning was not synchronized with the placement of the tower things, since it stated at 1 and not at 0. For example the 0-plate moved while the second digit changed at the first time :)
"Just ask a french person their feeling about bits" LOL so true.
Beautiful explanation.
Also, I think we can use base n for The Towers of Hanoi puzzle if we use n pegs, and constraint ourselves to move the disc to adjacent places.
So, if we took 10 pegs and the discs can move only to adjacent places in the puzzle, we should count in decimal system. Correct me if I'm wrong.
Amazing work! Really love your channel!
Amazing video, as always!
Wow, this is amazing and fascinating! 😀👍🏼
On sierpinski triangles, the bottom line is 2^n-1 moves long, representing the shortest path from all disk on the left to all disks from the right.
This is absolutely beautiful, thank you so much for appreciating this to the degree where you take the time to do these awesome animations!
I now know of 3 very separate ways of constructing the Sierpinski triangle:
Geometric rules (triangle, subdivide to 4 triangles, remove middle piece; iterate)
Chaos game (3 edges, a die; 1&2 correspond to edge 1, 3&4 to edge 2, 5&6 to edge 3; iterate (throw die) thousands of time from a random starting point; remove the first 50-100 steps)
The towers of Hanoi, as showed in this video.
Anyone know of any other way to produce this fractal?
Amazing video, as usual
this is beautiful. just absolutely beautiful.
thank you for doing this youtube channel!
Thank you so much for making those!
Great videos man! Subscribed.
started with a CS assignment to write a recursive solve for Hanoi and now I'm on here counting fractals... I think maybe this is the first video I've actually understood (I'm not very smart).
holy heck I wasn't expecting that. It all seemed very obvious until we got to the triangle and then wow
If you arrange the three pegs in a triangle rather than a line and view them from above, the sierpinski graph feels slightly less surprising in that the direction of each graph edge can be made to line up with the direction of the associated disk move.
Good job man i love your videos
I see how the nodes was placed out now.... Yay! Then I might code it later
3:38 as a French speaker, i laughed so hard at that lol
meaning dick because bits pronounced like bites (which be dick)
yes
[explaination for the english peeps]
Fantastic video!
Great! You see the big picture(s)! Greetings from Austria!
Ah, the bottom row and the long sides describe the most efficient way in the non-constraint puzzle. And this constraint puzzle is a 2d-version of it. If we need to go deeper, we need one more "solution" (as in the corners are solutions to a whole problem). Therefore this Sierpinski triangle in 3d would need one more pole. And 5-pole-game could be described with a super Sierpinski tetrahedron.
At 9:15 you show part of the graph, but you said that it was the constrained version of the puzzle, and the movement that you showed would be ilegal in the constrained version. I love all your videos btw, just something that i noticed, if you could explain me what it is or if it is a mistake, doesnt matter, your content is wonderful, hugs from Brazil
The following problem which I came across recently is also related to this video:
_A merchant had a forty pound measuring weight that broke into four pieces as the result of a fall_. _When the pieces were subsequently weighed, it was found that the weight of each piece was a whole number of pounds and that the four pieces could be used to weigh every integral weight between 1 and 40 pounds_. _What were the weights of the pieces?_
"Apparently it was first posed by Claude Gaspard Bachet de Méziriac in a book of arithmetic problems published in 1612, and can also be found in Heinrich Dorrie’s _100 Great Problems of Elementary Mathematics_."
It makes me so happy you called it a "triforce pattern"