Binary, Hanoi, and Sierpinski, part 2

Today, I want to share with you a neat way to solve the Towers of Hanoi puzzle just by counting in a different number system. And surprisingly, this stuff relates to finding a curve that fills Sierpinski's triangle. I learned about this from a former CS lecturer of mine, his name's Keith Schwartz, and I've gotta say, this man is one of the best educators I've ever met. I actually recorded a bit of the conversation where he showed me this stuff

so you guys can hear some of what he described directly. In case you're unfamiliar, let's just lay down what the Towers of Hanoi puzzle actually is. So you have a collection of three pegs, and you have these disks of descending size. You think of these disks as having a hole in the

middle so that you can fit them onto a peg. The setup pictured here has five disks, which I'll label 0, 1, 2, 3, 4, but in principle, you could have as many disks as you want. So they all start up stacked up from biggest to smallest on one spindle, and the goal is to move the entire tower from one spindle to another. The rule is you can only move one disk at a time, and you can't move a bigger disk on top of a smaller disk. For example, your first move must involve moving disk 0, since any other disk has stuff on top of it that needs to get out of the way before it can move. After that, you can move disk 1, but it has to go on whatever peg doesn't currently have disk 0, since otherwise you'd be putting a bigger disk on a smaller one, which isn't allowed. If you've never seen this before, I highly encourage you to pause and pull out some books of varying sizes and try it out for yourself. Just kind of get a feel for what the puzzle is, if it's hard, why it's hard, if it's not, why it's not, that kind of stuff. Now Keith showed me something truly surprising about this puzzle, which is that you can solve it just by counting up in binary and associating the rhythm of that counting with a certain rhythm of disk movements. For anyone unfamiliar with binary, I'm going to take a moment to do a quick overview here first. Actually, even if you are familiar with binary, I want to explain it with a focus on the rhythm of counting

which you may or may not have thought about before. Any description of binary typically starts off with an introspection about our usual way to represent numbers, what we call base 10, since we use 10 separate digits, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. The rhythm of counting begins by walking through all 10 of these digits. Then, having run out of new digits, you express the next number, 10, with two digits, 1, 0. You say that 1 is in the tens place, since it's meant to encapsulate the group of 10 that you've already counted up to so far, while freeing the ones place to reset to 0. The rhythm of counting repeats like this, counting up 9, rolling over to the tens place, counting up 9 more, etc. Until, after repeating that process 9 times, you roll over to a hundreds place, a digit that keeps track of how many groups of 100 you've hit, freeing up the other two digits to reset to 0. In this way, the rhythm of counting is kind of self-similar. Even if you zoom out to a larger scale, the process looks like doing something, rolling over, doing that same thing, rolling over, and repeating 9 times before an even larger rollover.

In binary, also known as base-2, you limit yourself to two digits, 0 and 1, commonly called bits, which is short for binary digits. The result is that when you're counting, you have to roll over all the time. After counting 01, you've already run out of bits, so you need to roll over to a twos place, writing 10, and resisting every urge in your base-10 trained brain to read this as 10, and instead understand it to mean 1 group of 2 plus 0. Then increment up to 11, which represents 3, and already you have to roll over again, and since there's a 1 in that twos place, that has to roll over as well, giving you 100, which represents 1 group of 4 plus 0 groups of 2 plus 0. In the same way that digits in base-10 represent powers of 10, bits in base-2 represent different powers of 2, so instead of a tens place, a hundreds place, a thousands place, you talk about a twos place, a fours place, and an eights place. The rhythm of counting is now a lot faster, but that almost makes it more noticeable. Again, there's a certain self-similarity to this pattern. At every scale, the process is to do something, roll over, then do that same thing again. At the small scale, say counting up to 3, which is 11 in binary, this means flip the last bit, roll over to the twos, then flip the last bit. At a larger scale, like counting up to 15, which is 1111 in binary, the process is to let the last 3 count up to 7, roll over to the eights place, then let the last 3 bits count up again. Counting up to 255, which is 8 successive ones

this looks like letting the last 7 bits count up till they're full, rolling over to the 128th place, then letting the last 7 bits count up again. Alright, so with that mini-introduction, the surprising fact that Keith showed me is that we can use this rhythm to solve the towers of Hanoi. You start by counting from 0. Whenever you're only flipping that last bit, from a 0 to a 1, move disk 0 one peg to the right. If it was already on the right-most peg, you just loop it back to the first peg. If, in your binary counting, you roll over once to the twos place, meaning you flip the last two bits, you move disk number 1. Where do you move it, you might ask? Well, you have no choice. You can't put it on top of disk 0, and there's only one other peg, so you move it where you're forced to move it. So after this, counting up to 1,1, that involves just flipping the last bit, so you move disk 0 again. Then when your binary counting rolls over twice to the fours place, move disk number 2, and the pattern continues like this. Flip the last, move disk 0. Flip the last two, move disk 1. And here, we're going to have to roll over three times to the eights place, and that corresponds to moving disk number 3. There's something magical about it. When I first saw this, I was like, this can't work. I don't know how this works, I don't know why this works. Now I know, but it's just magical when you see it. I remember putting together an animation for this when I was teaching this, and just like, I know how this works. I know all the things in it. It's still fun to just sit and just watch it play out. Oh yeah. I mean, it's not even clear at first that this is always going to give legal moves.

For example, how do you know that every time you're rolling over to the eights place, that disk 3 is necessarily going to be freed up to move? At the same time, the solution just immediately raises these questions like, where does this come from, why does this work, and is there a better way of doing this than having to do 2 to the n minus 1 steps? It turns out, not only does this solve Towers of Hanoi, but it does it in the most efficient way possible. Understanding why this works and how it works and what the heck is going on comes down to a certain perspective on the puzzle, what CS folk might call a recursive perspective. Disk 3 is thinking, okay, 2, 1, and 0, you have to get off of me. I can't really function under this much weight and pressure. And so just from disk 3's perspective, if you want to figure out how is disk 3 going to get over here, somehow, I don't care how, disk 2, 1, and 0 have to get to spindle B. That's the only way it can move. If any of these disks are on top of 3, it can't move. If any of them are in spindle C, it can't move there. So somehow we have to get 2, 1, and 0 off. Having done that, then we can move disk 3 over there. And then disk 3 says, I'm set. You never need to move me again. Everyone else just figure out how to get here. And in a sense, you now have a smaller version of the same problem. Now you've got disk 0, 1, and 2 sitting on spindle B, you've got to get them to C. So the idea is that if I just focus on one disk and I think about what am I going to have to do to get this disk to work, I can turn my bigger problem into something slightly smaller. And then how do I solve that? Well, it's exactly the same thing. Disk 2 is going to say, disk 1, disk 0, it's not you, it's me. I just need some space. Get off. They need to move somewhere. Then disk 2 can move to where it needs to go. Then disk 1 and 0 can do this. But the interesting point is that every single disk pretty much has the exact same strategy. They all say, everybody above me, get off. Then I'm going to move, OK, everyone pile back on. When you know that insight, you can code up something that will solve Towers of Hanoi, like five or six lines of code, which probably has the highest ratio of intellectual investment to lines of code ever. And if you think about it for a bit, it becomes clear that this has to be the most efficient solution. At every step, you're only doing what's forced upon you. You have to get disk 0 through 2 off before you can move disk 3. And you have to then 0 through 2 back onto it. There's just not any room for inefficiency from this perspective. So why does counting in binary capture this algorithm? Well, what's going on here is that this pattern of solving a subproblem, moving a big disk, then solving a subproblem again, is perfectly paralleled by the pattern of binary counting. Count up some amount, roll over, count up to that same amount again. And this Towers of Hanoi algorithm and binary counting are both self-similar processes, in the sense that if you zoom out and count up to a larger power of 2, or solve Towers of Hanoi with more disks, they both still have that same structure. Subproblem, do a thing, subproblem.

For example, at a pretty small scale, solving Towers of Hanoi for two disks, move disk 0, move disk 1, move disk 0, is reflected by counting up to 3 in binary. Flip the last bit, roll over once, flip the last bit. At a slightly larger scale, solving Towers of Hanoi for three disks looks like doing whatever it takes to solve two disks, move disk number 2, then do whatever it takes to solve two disks again.

Analogously, counting up to 111 in binary involves counting up to 3, rolling over all three bits, and counting up three more. At all scales, both processes have this same breakdown. So in a sense, the reason that this binary solution works, or at least an explanation, I feel like there's no one explanation, but I think the most natural one is that the pattern you would use to generate these binary numbers has exactly the same structure as the pattern you would use for Towers of Hanoi, which is why if you look at the bits flipping, you're effectively reversing this process. You're saying, what process generated these? If I were trying to understand how these bits were flipped to give me this thing, you're effectively reverse engineering the recursive algorithm for Towers of Hanoi, which is why it works out. That's pretty cool, right? But it actually gets cooler. I haven't even gotten to how this relates to Sierpinski's triangle. And that's exactly what I'm going to do in the follow-on video, part 2. Many thanks to everybody who's supporting these videos on Patreon. I just finished the first chapter of Essence of Calculus, and I'm working on the second one right now, and Patreon supporters are getting early access to these videos before I publish the full series in a few months. This video and the next one are also supported in part by Desmos, and before the next video I just want to take a moment and share with you guys a little about who they are and the fact that they're hiring. So Desmos is actually really cool. They make a lot of these interactive math activities for classrooms and tools for teachers. The real meat of their offering is in their classroom activities. For my part, I'm super impressed by just how well-thought-out these activities are from a pedagogical standpoint. The team clearly knows their stuff, and they know where they stand to make a difference in students' and teachers' lives. And like I said, they're hiring. They are always looking to bring in more good talent, whether that's engineering talent, designers, teachers, or whatever other skill sets line up with what they want to do. If any of you out there are interested in joining them, helping them make some of these great tools for teachers and students, you can check out the careers page I've linked in the description. Personally, I think they're doing some really meaningful stuff. I think their activities are building genuinely good math intuitions for students, and the world could use a few more talented people pointing their efforts towards education the way they do.