Binary, Hanoi and Sierpinski, part 1
Vložit
- čas přidán 24. 11. 2016
- Binary counting can solve the towers of Hanoi puzzle, and if this isn't surprising enough, it can lead to a method for finding a curve that fills Sierpinski's triangle (which I get to in part 2).
Thanks to Desmos for their help in supporting this video. They're hiring, and anyone interested should check out www.desmos.com/careers
Thanks to all Patreon supporters as well, you can support and get early access to future "Essence of" series here: / 3blue1brown
I also want to give a special shoutout to the following patrons: CrypticSwarm, Ali Yahya, Dave Nicponski, Juan Batiz-Benet, Yu Jun, Othman Alikhan, Markus Persson, Joseph John Cox, Luc Ritchie, Einar Wikheim Johansen, Rish Kundalia, Achille Brighton, Kirk Werklund, Ripta Pasay, Felipe Diniz, Chris, Curtis Mitchell, Ari Royce, Bright , Myles Buckley, Robert P Zuckett, Andy Petsch, Otavio good, Karthik T, Steve Muench, Viesulas Sliupas, Steffen Persch, Brendan Shah, Andrew Mcnab, Matt Parlmer, Naoki Orai, Dan Davison, Jose Oscar Mur-Miranda, Aidan Boneham, Brent Kennedy, Henry Reich, Sean Bibby, Paul Constantine, Justin Clark, Mohannad Elhamod, Denis, Ben Granger, Jeffrey Herman, Jacob Young.
How is this the first time I hear that _bit_ is short for _binary digit_...
Mind blown.
Yeah I needed a moment after that,
Raphael Schmidpeter same tho
TheGerogero ikr, i counted up to 790 in binary without understanding what bit meant.
TheGerogero same
Does that mean a digit in the ternary system is...
A tit?
I am software developer (who also has a love for math) and it never once occurred to me that counting was a recursive action. I am continuously amazed at how elegant and simple your videos are and how effective they are at showing complex ideas in an approachable way. Thanks for all your hard work!
@@vairavanrenganathan4752 I don't want to put words in his mouth but I believe that he sort of means self-similar. By that, I mean that you can break it down into scaled down problems that are similar in procedure to solve.
same
Any cycle can be represented as a recursive action. Any recursive action can be represented as a cycle.
You might be interested in the Church encoding of numbers in Lambda Calculus which is a mathematical analog to functional / recursive programming (as Turing machines are to imperative languages)
eəėëėəe
I simply love your videos! I'm a mathematics student, so I'm used to the joy of understanding, but that doesn't make it any less exciting! And your animations are a wonderful, powerful and beautiful help in this delightful process!
I may be repeating myself but nonetheless: Thank you! Keep up the great work! :)
Always nice to hear from an enthusiastic math student, and thanks for the kind words. Keep loving math.
Same here :) I'm a computer science student, and I love how you visually explain problems, it makes everything a lot easier to understand. I would have had a much harder time understanding this in a textbook, especially the concepts you explained in part 2. I hope that sometime in the future, we will integrate visual material like this into out science lectures
I've used Desmos for a little over a year now, and I'm sad that my math classes never use it. I mainly just use it for my game development and for math-fun. It's the best math-function graphing tool I've ever used.
I saw this puzzle 50 years ago in high school. My classmates were struggling with it. I just sat down and did it without hesitation. It has always been obvious to me. I earned a Masters Degree in Computer Science. It seemed to me trivially obvious that this puzzle was binary counting. 3Blue1Brown explains this beautifully.
another great perspective that I just realized...count up how many times each disc /has/ to move, starting from the bottom. disc n has to move just once, disc n-1 has to move twice (once to get off of disc n and once to get back on again), disc n-2 has to move four times, etc
Your videos captured my attention so well in your calculus lectures, that I finally dispelled the notion that I was not a math person, and simply needed to try harder. Finally going back to school, and no longer avoiding math intensive fields! Seriously though, this video is so cool, my girlfriend generally isn’t interested in this kind of stuff, but she loved this as well. Thank you, for working hard to put this stuff out.
I never thought about it, I just found it so simple once I found the pattern, but I never could've imagined it'd be hiding something more complex and so beautiful
I've never even taken a CS class but this is so fascinating! I love seeing videos appreciating the thrilling cohesiveness which seems to appear in every area of mathematics. Absolutely adore these videos, thanks for putting them out there!
Wow, just solved a programming task for the Towers of Hanoi, and remembered that this video existed. Thanks for saving the day _and_ blowing my mind.
This one was incredible! the math was really cool and the animations were insane!
and you're supported by the best graphing calculator ever!!!
+
You probably meant "you ARE the best graphing calculator ever".
"Counting is self-similar" -- fantastic and thought provoking!
So nice ! I taught the Hanoi towers when I was teaching algorithmics, because it was the simplest example I could think of with exponential complexity, but I never knew this trick with binary counting !
There is an error in the transcript at 7:55 : the number of steps required is 2^n - 1, not 2^(n-1).
Honestly, these two videos are my favourites of yours. I’ve rewatched them so many times. SO COOL.
I always felt like counting in binary when solving towers of Hanoi! That's amazing now that I understand why.
I really loved math when i was studying it at school and you give me so much unsuspected insight into topics i thought i knew very well. Thank you so much. After each of your videos i feel that i learned something new.
Fun trivia: According to legend, when the full 64 disc puzzle is solved, the world will end. Assuming 1 move per second, it would take 2^64-1 = 1.84*10^19 seconds or 585 billion years, which is incidentally the time it takes until the last star in the universe burns out.
Program it and it'll be done very soon.
1 move per second is way too slow (for a computer).
True... True
A red dwarf's lifespan is EASILY into the trillions of years. So your anti-science fact is false.
@@shreeganesh441 use delay(1000)
Once in year 7 or 8 I was in maths and at the end of the class the teacher asked the class how we could improve our understanding of the content covered in class that day. Some students suggested things like calculating the cost and change (if paid in cash) of grocery expenditure. Another said "counting" and the teacher laughed, and said "counting what?", the student said "anything", the teacher laughed again but louder and with the rest of the class before saying "No [name], I don't think counting is going to help".
Looks like counting is pretty useful right about now.
Could be s specific question
R
Cool profile pic
A simpler rule (only needing to count in base ten (or not at all when you got into the rythm) I noticed when trying this out:
- On an odd numbered move: Move the 0-piece once to the right (or left, works both ways as long as you dont switch direction)
- On an even numbered move: Move the largest piece you can move (which is never the 0-piece) to the only legal place
Which is, of course the same as counting in binary, but a little simpler to put to use imo :)
I really like your use of the Computer Modern typeface!
Wow, this video was really cool! It's awesome how something so seemingly mysterious and strange seems obvious once you get the right perspective on it. Can't wait for the next video!
Holy! This is absolutely amazing. I solved this puzzle for/with a student of mine and came to these conclusions, but the binary counting perspective is simply mesmerizing. Thank you for this video!
Thank you. This was absolutely amazing to watch and blew my mind. I had never even considered thinking about the problem like this and I know I'm going to look at other problems and see if this pattern can be applied there as well.
Love all your videos. Easy to follow the lectures and the graphics surely make an awesome impact on understanding. Thanks :)
Your channel is absolutely gold dude. Keep up the good work. It's so refreshing to see university level mathematics displayed so entertainingly and so clearly. Thank you.
Wouldn't it make more sense for the binary numbers at 6:05 and 11:20 to be coloured exactly the opposite way they are, i.e. leftmost digit bright blue and rightmost digit dark blue? That way the colour of the digit that flips corresponds to the same colour of disk that's actually moved.
Ooh, good catch! What's funny is that I did it right for the ternary counting in the next video. Ah well, silly mistakes have a pernicious way of sneaking into all my videos, you know?
@@3blue1brown So modest!🙇🏻♀️
@@3blue1brown It's the silly mistakes that do not affect the content of the video that much that remind the rest of us that we are in fact listening to an incredibly talented youtuber telling us the wonders of (probably) his favorite subject.
@@efulmer8675 Are you implying Cyanogenoid is not in fact listening? Of course they are.
@@msfundio No, I'm not suggesting that at all.
Super great video 3Blue1Brown! That connection to recursion is so cool!
On Desmos: it's awesome. I probably use it every day. It's awesome!
Thanks. Great video. I was blown away when you showed the relationship between hanoi towers and binary counting. Way to go!
Your videos helped me out so much when I was learning neural networks, and they're saving my life again :) Thanks!
You missed the fact that odd numbers are always moved left and even numbers are always moved right.
nice catch!
Or vice versa. I remember in one of the jump-start CD games, you had to solve this a lot. Except, the location of the final stack mattered. So if you had an odd number of boxes, the first box would move to the location of the final stack. If even total, to the stack you aren't supposed to end up on.
two steps forward, and one step back!
Thanky fer ifnooh (why do i write like this)
James Maxa It’s text in a window; you have time to look at it and correct stuff before submitting it!
I always noticed the recursive property of that problem but could never really mathematically formulate what it was. It's satisfying to get the answer by such a beautiful piece of math. Thank you and keep up the really good and wonderful work.
There's something you overlooked at least in this video and that is quite beautiful. The even-numbered disks either move one space to the right or two spaces to the left, and the odd-numbered ones do the opposite: move one space to the left or two spaces to the right. It's determined by the binary number that each disk adds but modulo 3.
Neat video. You manage to communicate it in a way that's comprehensive, yet doesn't get boring when you reiterate things. That's impressive! There's one thing I think you fail to mention, and that is that the self similar structure isn't particular to binary numbers, so all the arguments of rolling over and recursion work just as well for other bases. What makes binary appropriate is that smallest "subproblem" of moving a single disk is modelled by a bit, as it can be either moved or unmoved.
Oh the memories!
The very first program I wrote for my Assembly Language class project was the solution for the Hanoi puzzle on a Dec PDP11-45 back in 1975.
Man, I really appreciate your videos. I must say that I a computer scientist of sorts (Information Systems actually) so binarry is no problem for me and that I loved Tower of Hanoi since I first saw it.
So normally to solve the puzzle, I just look if the the ammount of disks, check if it's odd or even to tell the direction of cycle I'll do with the smaller disk, left or right repectvly. Then I just know that I must start moving the smaller according to the cycle, after that, do an obrigatory move, moving smaller, obrigatory move, and so on.
Even though I know exactly the logic of how to do it in the most efficient way, I never saw any connection of the puzzle and the rhythm of bynary counting as you showed. I was simply amazed.
Thank you, keep doing this amazing work for us.
Your visuals keep getting better! Nice!
Your videos are all first rate. This one, however, is masterful. It should be the first result presented when one searches for the Hanoi problem.
Marvelous again.
When I was younger, my grandpa taught me a slightly different version: A larger disk not only cannot stop over a smaller one, but it cannot pass over it at all. This essentially makes the game longer, which I suspect was the goal of my grandpa.
I kind of remember talking about it with a friend a couple years ago, and I think we came to the conclusion it was very much like classic Hanoi, but with base 3 instead of base 2. Maybe I should take out a pencil and check that again..
EDIT: Shame on me, I should have binged the series like a true 3Blue1Brown fan before posting this.. Keep up the good work!
Really good video!! Never thought of solving the towers of Hanoi with Binary. Love it!
Great video you explained everything so well I could feel why counting in binary works in a way others haven’t been able to do.
As someone who's in the middle of a computer networking course, I really like the way you explained binary. While I already know how it works (thanks IPv4!), your explanation is really good, and if I have to ever explain binary to someone else I'll probably have to borrow from this.
Wow. This is already awesome !
And now : let's check part 2. :)
It's awesome. In the end of your last videos i just smile. Really great, keep it up.:)
well done. I like to think of periodic boundaries where even number disks go one way and odds go the other.
Binary digits? I'd have called them bidgits.
"Not lazy enough. Let's shorten it down to bits." --- Computer Scientists.
bigits just didnt have the same ring to it
SquareWaveHeaven bigots*
@@jadondavid8272 no
I’ve heard of another thing: mijits
tower of hanoi puzzle is pretty neat. i had to write a recursive method in java that would "solve" the puzzle recursively for any amount of discs. the craziest thing was how much time it took for the compiler when you added a crazy amount of disks like 20 or 50.
Everyone admires your brilliance when you can break everything down into fundamental components.
I just realized that 2048 was just making us count in binary
MrLusass Well, decimalized binary
You should check out Threes. 2048 plagiarised that game pretty heavily and is not nearly as deep and compelling. It has a very similar principle but is more complicated.
really, you just noticed that now
When will there be a game that is using base 1? Base 1 is my favorite base
@Johnny Lee Does he have no fingers?
Oh man, I know desmos was a sponsor of this video, but I gotta say, I'm a computer engineering university student, and I use the graphing app from them all the time. I do some very complicated mathematics most of the time, and it's really helpful to be able to put a complicated function in and add some parameters as sliders to see how it affects the shape of the graph. I actually just used it the other day and noticed they added integrals, and I was super excited to see that.
On a more related note, this video was excellent. I took an algorithms class in which we studied towers of hanoi solving methods. However, my professor didn't really show the connection between the recursive algorithm and counting in binary. Really insightful stuff.
amazing video, thank you for visualizing everything
You're doing awesome work. Keep it up! :)
Your channel is lovely. a fantastic corner of CZcams.
Brilliant content thank you so much and please continue
I have been struggling with finding the best strategy for this game and you revealed it!!! :O
Great, as always.
Very cool! Great explanation!
Wow, this is amazing and fascinating! 👍🏼😀
This makes me so happy, math like this just is awesome.
Awesome, You have to make a lot of these videos !
Interesting video! I tried a little experiment. In the unrestricted case If there are 3 stones stacked on top of each other labeled 0, 1, and 2, then the next column position of the rock represented by a trit change can be calculated by 3^label modulo columns. I tried this with 4 columns and it works out, but for 3 or 5 columns, the direction of the move toggles left and right.
Hi @3Blue1Brown I want to share a slightly different interpretation. The process of solving the Tower of Hanoi reminds me classical beginner's programming problem of swapping two variables content. You perfectly know that we need a third variable to swap the content of two of them, this is because we have the constrain that we can't send the information from one place to the other at the same time and without loosing one of the two (I call it quantum swapping :). That's exactly the analogous case in the Hanoi game "you can't put a bigger square on top of a smaller one" this constrain recast the game in a "swapping game", where the sticks works as variables. You are forced to use another stick and therefore follow the binary pattern. Can we apply the XOR trick by achieving a quantum swapping also in the Hanoi game? :) Thanks for your amazing work, a MS CS student.
Lol you can swap the values in python
yes, tower of hanoi is like copying a stack to a new place in memory with the order of sequence remaing intact all the time.
I think you have the best music taste for any CZcams channel.
Love the smooth animation.
Always wonderful.
Hey ! Loving your videos.
you're in contact with desmos! ask them to integrate the triangle thing for log, pow, root in their graphing calculator! that would be a huge step for getting more people to using it (hopefully) - btw i love these videos thank you so much for all of this. i have learned so so so much from you and i really appreciate the way you explain things
I loved it. Thanks.
Thank you for all the videos. Long live
+
I'm going to try it with my child, love the way to correlate to binary with hanoi towers, and the recursive approach
This is the first video where I knew everything prior to watching it. Defiantly a different feeling when watching.
as someone who is still in highschool and looks forward to studying CS in uni, this is a really nice video and helped me a lot :D
awesome stuff thanks!
I remember when I programmed this for the first time, it was one of my first times programming as well. They never explained us anything about the problem, I got to understand that it was recursive (although I didn't know that term formally), but didn't understand it completely, so I looked up for the flow diagram and implemented it.
They didn't believe that I solved it, they were right, although an explanation like this could've helped me.
Very insightful.
I actually remember when I first noticed this. I didn't really understand it in such a formalized way, though.
HOW COULDN'T I THINK OF THIS??? SO CLEVER!
Beautiful video~~~~~~and expecting for your Higher Mathematics series~~~~~~
This is EXACTLY why I'm not teaching anymore. I couldn't explain it better. Thank you.
In computer science class the towers of Hanoi problem was used as an introduction to recursive programming. Interesting to see a different way to look at it.
The problem with "move it over once" is that the way I learned the rules of the puzzle is that you had to go from _leftmost_ peg to _rightmost_. So if you started with an odd number of rings, you would need to move it over twice (or once the opposite way). The way I always solved it was:
odd numbered tower/subtower -> move next disc to destination you want the whole tower/subtower to be at
even number -> move next disc to non-destination
This pattern works throughout the whole puzzle, and I assume it's basically the same as the binary thing, but harder to keep track of. I used to obsessively do this puzzle with playing cards (i didnt have pegs and rings), and i went up to 13 one time (took 2-3 hours I think?). Every new card would take about twice as long, I guess because 2^n (oh hey, binary!!)
If you picture the pegs in a circle instead of a line you could say that when the number of circles is even you do the first move clockwise and if it's odd you do it anti clockwise (or the opposite, depending on how you set up the circle). Basically the direction of the first move would be (-1)^n, where n is the number of discs (and then you decide which one between +1 and -1 is clockwise)
@@kwarsha you can do that thing in a circle in opposite direction too. Like start the disc 0 to move in anti clockwise and disc 1 to clockwise. Will end up at the right solution. Circular things work in both directions. It seems In that case the kind of thumb rule (-1)^n will not work. Agree?
Oh my god this video just blew my mind!
In a Numberphile video about this, I learned that disks with like parity are never consecutive on the same peg.
This really IS very cool. makes a neat party trick too
Yay, I love desmos!
This is one of your best videos! It really appeals to my sense of pattern :) One small note: I think the plurals of "two", "four" and "eight" are "twos", "fours" and "eights". No apostrophes are needed. Maybe this confusion arises because apostrophes are often used with digits to reduce ambiguity, e.g. "10's", "100's"; this isn't the case for numbers spelt as words.
+
Either is correct here but they carry different nuances.
Pedantry alert!
Twos is the plural of two, so that there are three twos in six, as you correctly say.
But two's indicates ownership or belonging. Think of when we say my girlfriend's implying my girlfriend's place.
(Note that's different from my girlfriends which would suggest polyamory).
So the two's implies the place where the twos are listed, the eight's the place where the eights live, and so on.
@@trueriver1950 You are logically quite correct but - forgive me - idiomatically wrong. Just because you can imagine using "two's" to stand in for "two's place" doesn't mean that it's common usage. As far as I know, the construction you describe applies to people's homes, but not digit positions. Of course, it could be that everyone's been doing it like that for decades and I simply hadn't realised... in which case, my apologies.
True story: my dad was a primary school teacher a long time ago, and sometimes one of his pupils would say something like "I'm going up my Nan's." His reply was usually something like "would you like to borrow a ladder?" He was such a joker!
... numbers spelled as words ... "spelt" is a grain.
@@wiregold8930 It's a perfectly correct British spelling.
keep doing this, you are great
“You move it where you’re forced to move it” at 6:45 can be described as “move the piece mod(X/2)+1 to the right”, where X is the piece number (if the smallest piece is 0 as shown)
Brilliant!
Thank you !
Dude! Theoretically every recursive program can be represented by a procedural program and this video made me realize the procedural version, which is really cool!
1) rename disks beginning with 1 instead of zero 2) each disk moves exactly as follows: excluding the peg that the disk is currently on, count the remaining pegs left to right the number times equal to the number of the disk 3) Here's the really cool part: move disk n where n is the position of the binary digit flipped to a one while counting in binary up to 2^(x-1) - 1 where x is the number of disks.
That sounds horrible, but if I had a towers of hanoi I could show you the algorithm works by counting on my fingers it's so easy.
Back (many years ago) when I was learning early coding, the Towers-of-Hanoi puzzle was the way I was taught recursion. You solve for N by solving for (N-1) and then adding one move, and then solving (N-1) again. And so on...
I really like the parallels between this and Gray code, a binary system in which each consecutive number only differs by one bit. The bit that is flipped each time is the same disc that would be moved in towers of hanoi! That is actually how I found this, coming from gray code. Funny how it is the other way around, rather than looking at a puzzle and finding binary, I looked at binary and found a puzzle!
If I wasn’t busy with anything I’d watch all of your videos non stop, well I do that now anyway but I get a headache because I’m trying to juggle it with things I’m doing already.
This is mind blowing, Next time you get towers of hanoi in an interview make sure to implement this 😅
Amazing video
I think you could have highlighted the fact that you are moving the piece one right, and if you can't move it one right, two right. Moving straight left in the animation, in the case of skipping over from the middle position or the rightmost position, had me confused for a while. This mechanic also neatly explains why the piece moving can never move back onto the piece that was "trying to get rid of it", which was what I didn't originally understand.
Great video though! Thanks!
A minor point: The usual term is _tens place_ , not "ten's place." The apostrophe implies possession, as if the digit there is taking the place of ten. However, the usual term is plural instead, meaning that the number in that place represents the number of tens. So 35 has 3 in the tens place and 5 in the units place because it is three tens and five units.
The colours of the binary digits are in opposite direction to the disc colours :) Never the less, great video!
I've never enjoyed a puzzle so thoroughly xD
I have a physical model of this that I solved myself, and when he started explaining binary this way, I got chills! This is absolutely beautiful, especially because I am familiar with it, but never thought of it with binary! I also really like the serpinski map of the entire game, which is a clear map of how to get between any point in the game. This is amazing, and made my day. Thank you.