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 want to go check it out Here, in this video, I want to describe a constrained variant of that puzzle and how it relates to finding a curve that fills Sierpinski's triangle. The problem variant is that ... you can think 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 So, for example, in the previous one, we start by moving disc 0 to B, and the next move was to move disc 1 over to C, but you can't do that because you can get 1 straight over to C. Exactly. So, it's more complicated. But the idea for this modified version is still similar. So if I want to move disc 3 -- let's say I'm trying to get it from A to C. So, as before, I can't move disc 3 unless this tower above it, 2, 1, and 0, 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 want to do is take this tower of 0, 1, and 2 and somehow -- I don't know -- get it to thing C then move disc B over, then get it off of C, back to A Then move disc 3 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 2, solve for 2 again, move disc number 2, 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 1, which just involves moving disc number 0 twice. As with the unconstrained case, this is going to 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 0, 1, and 2 over to peg C if you plan on moving disc number 3. And you have to move it back to A in order to move disc 3 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 3, also known as ternary. Here, let's take a moment and talk about what base 3 feels like -- what the rhythm of counting there is. So, as you know, our usual counting system, base 10, has ten separate digits, and binary, or base 2, has two separate digits, so ternary is a system of representing numbers where you only have three distinct symbols available -- 0, 1, and 2. I don't even know what you call them. So, it's not a bit; it's not a digit; is it at trit? I think we were talking about this earlier. 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: 0, 1, 2. Then, you have to roll over to a second trit in the threes place. Then, you count to 4, which is 11; 5, which is 12; and you have to roll over again, to 20, representing six. Then, 21, 22, at which point you have to roll over twice, to the nines place, writing the number nine as 100. Just like base 2 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 going to mirror the recursive pattern for solving the constrained hours 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 trip, move disc number 0. So for the first two moves when you're counting, 1, 2, you'll be moving disc 0. Whenever you roll over just once to the threes place, such as when you count from two up to three, represented by 10, you move disc number 1. And continuing on like this, you'd flip the last; move 0; flip the last; move 0; roll over, writing 20; and then move disc 1. then, twice more, you flip the last and move disc 0. Then, whenever you roll over twice to the nines place, you move disk number 2. Again, it's pretty fun to just sit back and watch this play out. It takes a while, though. For four discs, you're going to have to count all the way up to 2222, which is ternary for 3⁴ - 1, which is 80. That means that solving this involves 80 steps. Nevertheless, like I said before, this is the most efficient solution. But this also then gives you something very cool; you can ask, how many different configurations are there 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 3⁴, 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 3⁴ - 1 steps, which means from start to end, you're going to 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. 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 going to 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 going to be connected to this one, which is the result of moving disc 0 over to peg B. And both of those are connected to this one, which is the result of moving disc 0 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 going to be part of one of these triangles somewhere in the graph. You just consider what happens as you freely move around disc number 0 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 1 from peg A to peg C, so they're going to 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 meta-triangle when you consider all the movements of disc 1. Each little clump of three nodes here represents a different position for disc number 1, and the Triforce pattern as a whole represents all configurations you can get by moving around discs number 1 or 0. And self-similarly, a movement of disc number 2 gives you a bridge from one of these Triforce patterns to a new one. And the three possible places where disc 2 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 2. That only happens in those very special configurations where disc 1 and disc 0 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 going to 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. For the final animation here, I want to show you guys what those paths look like for Sierpinski graphs of higher and higher order. But first, some thanks are in order for the fine funders of this video. As always, my sincerest gratitude to the Patreon supporters. Like I mentioned in the last video, I've started working on an Essence of Calculus series, and so far, I'm really appreciating the feedback the Patrons are giving. This pair of videos was also supported by Desmos. Like I said at the end of part 1, Desmos creates these really meaningful interactive math activities for classrooms and pretty great tools for teachers. And importantly, they're hiring, so anyone out there interested should definitely check out the careers page that I've linked in the description. And by all means, reach out to them if you're interested. There are a lot of edtech companies out there that make some flashy tools in the hope of bringing modern technology to math curricula, but often there's not actual pedagogical substance underlying the tech. I really do think, though, that Desmos is going about things the right way. I was surprised by the amount of collective teaching experience that they have among their team, and even the non-teachers that I met there are really thoughtful and really well-versed when it comes to educational research. The result is that their activities actually address what's lacking and needed in a student's education. So if you're interested in the edtech space, and if you're interested in going to a place that, you know, actually matters, I highly encourage you to take a look. All right, so, for this last animation here, I'm going to show the path that walks through the Sierpinksi 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.
