Pop Video: Binary, Hanoi, and Sierpinski, Part 2

Grant Sanderson • 3Blue1Brown • Boclips

Binary, Hanoi, and Sierpinski, Part 2

12:13

Video Transcript

Welcome back! So, in the last part, I showed a way to solve Towers of Hanoi just by counting up in binary, a solution that I learned from computer scientist Keith Schwarz. If somehow you landed here without watching that, you probably wanna go check it out. Here, in this video, I wanna describe a constrained variant of that puzzle and how it relates to finding a curve that fills Sierpinski’s triangle.

KEITH: The problem variant is that the, you know, some- you can think of these discs are in a line. You’re only allowed to move a disk from one spindle to an adjacent one. And, so, now the question is, solve Towers of Hanoi.

GRANT: So, for example, like in a previous one, we start by moving disc zero to B. And the next move was to move disc one over to C. But you can’t do that because you can’t get one straight over to C.

KEITH: Exactly! So-so it’s more complicated. But the idea for this modified version is still similar. So if I wanna move disc three, let’s say I’m trying to get it from A to C. So, as before, I can’t move disc three unless this tower above it — two, one, and zero — are out of the way. So, ultimately, I’d like to get this tower to be not blocking it. But there’s two ways it can block it now. So, previously, it just had to not be on top. Now it has to not only not be on top, it can’t be adjacent either. So, really, what I wanna do is take this tower of zero, one, and two and somehow, I don’t know, get it to thing C, then move disc three over. Then get it off of C back to A. Then move disc three from spindle B to spindle C. And then move that tower all the way back.

The smaller case breaks down essentially the same way. You solve it for two discs, move disc number two, solve for two again, move disc number two, then solve for two discs yet again. As you keep subdividing in this self-similar pattern, expanding each subproblem into its own set of subproblems. Eventually, you get to the smallest subproblem of them all, moving a tower of size one, which just involves moving disc number zero twice.

As with the unconstrained case, this is gonna give you the most efficient solution, since at every scale you’re only doing what you have to do. You have to move that subtower with zero, one, and two over to peg C if you plan on moving disc number three. And you have to move it back to A in order to move disc three again. And you have to move it all the way back to C a third time. There’s just never any room for inefficiency once you break it down in terms of subproblems like this. And just as the unconstrained puzzle mirrored the pattern of counting in binary, the breakdown of this constrained problem is mirrored by counting in base three, also known as ternary. Here, let’s take a moment and talk about what base three feels like, what the rhythm of counting there is.

So, as you know, our usual counting system, base 10, has 10 separate digits and binary, or base two, has two separate digits. So ternary is a system of representing numbers where you only have three distinct symbols available, zero, one, and two.

KEITH: I don’t even know what you call those. So, it’s not a bit; it’s not a digit; is it-is it at trit? That just- I-I think we were talking about this earlier. Like it just doesn’t sound right.

They are indeed called trits. But hey, if that sounds a little bit off to you, just ask a French speaker how they feel about our convention of calling binary digits “bits”.

Anyway, back to what we were doing, let’s think about the rhythm of counting in ternary. You start by just counting through the trits, zero, one, two. Then, you have to roll over to a second trit in the threes place. Then, you count to four, which is one, one; five, which is one, two; and you have to roll over again to two, zero, representing six. Then two, one; two, two, at which point you have to roll over twice to the nines place, writing the number nine as one, zero, zero. Just like base two and base 10, there’s a certain self-similarity to this pattern. At all scales, it looks like counting up to some amount, rolling over, counting to that same amount, rolling over again. Then counting to that same amount a third time.

But this is the pattern that we just saw with the constrained Towers of Hanoi. Do a subtask, make some kind of larger movement, do a subtask, make that same larger movement. Then do the subtask a third time. So just like binary counting mirrors the solution to the unconstrained Towers of Hanoi, counting in ternary is gonna mirror the recursive pattern for solving the constrained Towers of Hanoi. This gives a really nice and methodical way to solve the constrained problem just by counting. Every time you’re only changing that last trit, move disc number zero. So for the first two moves when you’re counting one, two, you’ll be moving disc zero. Whenever you roll over just once to the threes place, such as when you count from two up to three represented by one, zero, you move disc number one.

And continuing on like this, you’d flip the last, move zero; flip the last, move zero; roll over writing two, zero; and then move disc one. Then twice more, you flip the last and move disc zero. Then whenever you roll over twice to the nines place, you move disk number two. Again, it’s pretty fun to just sit back and watch this play out. It takes a while, though. For four discs, you’re gonna have to count all the way up to two, two, two, two, which is ternary for three to the fourth minus one, which is 80. That means that solving this involves 80 steps. Nevertheless, like I said before, this is the most efficient solution.

KEITH: But this also then gives you something very cool. You can ask, “How many different configurations are there for-for Towers of Hanoi?”

Actually, let’s take a moment and think about this. How many total configurations of discs on pegs are possible, where the disks on a given peg have to be in descending order of size? The answer is three to the fourth, 81 possible states that your puzzle can be in. To see this, notice that there are three choices for where to put that biggest disc. Then three choices for where to put the next biggest disc. And for each successive disc, you have three choices for where to place it.

And remember, this process of solving by counting in ternary involves taking three to the fourth minus one steps. Which means, from start to end, you’re gonna hit 81 different configurations. And if you think about it, it can’t hit a given configuration twice. If it did, there would be some more efficient solution out there by working up to the first time where you hit that configuration, then skipping over everything in between that and the second time you hit that same configuration, then just continuing.

KEITH: I have, in a sense, sort of a grand tour. This will not only solve Towers of Hanoi. This will go through every single possible configuration of the disks.

Pretty cool, right? Well, here’s where things get awesome. For those of you familiar with graphs, there is a very beautiful structure to these configurations. What I’m gonna do is represent each one of these configurations with a dot, a node in our graph. Then, we say that two different configurations are connected if you could move from one to the other with some legal Towers of Hanoi move. And this time, I mean an unconstrained move. So configurations are still considered connected even if it requires a move from peg A to peg C. When you go through and connect all of the configurations like this, finding all the edges that represent some kind of move, the graph structure for Towers of Hanoi has this suspiciously familiar shape.

Now, let’s zoom in on it, and think about where this pattern is coming from. For example, this node here representing the start state with all the discs on peg A is gonna be connected to this one, which is the result of moving disc zero over to peg B. And both of those are connected to this one, which is the result of moving disc zero to peg C. These three configurations make up a little triangle in our graph. That is, the three configurations are all mutually connected to each other. In fact, any configuration is gonna be part of one of these triangles somewhere in the graph. You just consider what happens as you freely move around disc number zero among the three pegs.

Now, to understand how these little triangular islands are interconnected, take a look at these two nodes. They differ only by a movement of disc number one from peg A to peg C. So they’re gonna be connected by an edge. This edge is kind of a bridge between two different triangle islands. In fact, those two triangles, along with this other one, form kind of a metatriangle when you consider all the movements of disc one. Each little clump of three nodes here represents a different position for disc number one. And the triforce pattern as a whole represents all configurations you can get by moving around discs number one or zero.

And self-similarly, a movement of disc number two gives you a bridge from one of these triforce patterns to a new one. And the three possible places where disc two can live give us these three separate triforce patterns, which are each connected by a little bridge. The fact that there are only two nodes in one of these triforce patterns that has an edge going out of the pattern itself is just a reflection of the fact that it’s hard to move disc number two. That only happens in those very special configurations where disc one and disc zero are both out of the way.

As you consider more and more discs, this pattern continues. The graph structure for Towers of Hanoi configurations is one big Sierpinski triangle. Isn’t that crazy?! So now let’s think about what it means for this method of solving the constrained problem by counting in ternary to walk through all possible configurations. What it’s gonna give us is a way to wander through this graph and hit each node once and only once. This is crazy to me. If you just look at the Sierpinski graph structure, it’s not clear at first that such a path is even possible. And yet, we found one just by counting. If that’s not beautiful, I don’t know what is.

Alright! So for this last animation here, I’m gonna show the path that walks through the Sierpinski graph according to the way in which ternary counting solves the constrained Towers of Hanoi puzzle. If I fade out that graph just to emphasize the path, here’s what it looks like for higher and higher orders, corresponding to Towers of Hanoi with more and more discs. What you’re seeing is very similar to the idea of space-filling curves that I talked about in the Hilbert curve video. It’s just that the limit here fills a fractal instead of the square. Isn’t that crazy?! You can have a curve that fills Sierpinski’s triangle, which I totally don’t think of as a curve-type thing.

Nagwa uses cookies to ensure you get the best experience on our website. Learn more about our Privacy Policy.