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 triangle. I learned about this from a former CS lecturer of mine, his name is Keith Schwarz. And I’ve got to say, this man is one of
the best educators that 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. It’s weird, I’m not normally the sort of person
who likes little puzzles and games, but I just love looking at the analysis
of puzzles and games, and I love just looking at mathematical patterns and (ask): where does that come from? In case you aren’t 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 discs 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 set I pictured here has five discs,
which I’ll label 0, 1, 2, 3, 4, but in principle you could have as
many discs 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 disc at a time, and you can’t move a bigger disc

한국어 자막좀요 ㅠㅠ

#### Lex Nellis · November 16, 2018 at 8:23 am

This is the first video where I knew everything prior to watching it. Defiantly a different feeling when watching.

#### Aperson101 · November 20, 2018 at 5:33 am

Why is this puzzle has the same names as my country’s capital city?

#### Guy3nder · November 20, 2018 at 5:27 pm

this recursion reminds a lot of how in physics certain principles repeat in different models. how you can see laws in physics repeat in chemistry, then in biology, and then even down to sociology and psychology. the most basic ideas in science apply to all scientific fields in some way and remain amazingly consistent. this is why i love math and science and what really makes religion look like horsecrap next to it.

#### My Username is Pointlessly Long and Intimidating · November 23, 2018 at 9:05 pm

This only works if the towers are allowed to be completed on the 2nd tower instead of the 3rd rip. It works in similar ways either way.

#### hy nguyen · November 25, 2018 at 2:32 am

i would like to know similar channel to this but in physics subject. Does any one have a list of name? thank you so much.

#### Laurin Neff · November 26, 2018 at 8:46 pm

There are 111 types of people: those who understand binary, those who don't understand binary, and those who didn't expect a unary joke here

#### Gabriel-Teofil Mititelu · November 28, 2018 at 10:45 am

@3Blue1Brown, any idea if this also works on a modified ToH problem like, N disks, but with M pegs?

#### Joe Smith · November 29, 2018 at 1:54 pm

Could write this in assembly the moving of bits to complete the disk tower

#### Nicodemeus · December 9, 2018 at 1:59 am

"Its not you its me" im dying

#### Rizky Maulana Nugraha · December 11, 2018 at 1:06 pm

Binary works because the algorithm reduce to binary complexity for each actions.
This is useful when you measure it's complexity.
For each depth of recursion, we essentially do 1 + 2*(steps for that depths).
To ilustrate, let f(N) be the number of steps needed to move the pegs efficiently.
It is a recursive function.
For f(N) the steps involves:
1. Moving the rest of the pegs (N-1) means f(N-1) steps
2. Moving the bottom peg count as a step
3. Moving the rest of the pegs again, means f(N-1) steps.

algo 1 and 3 is the same, so it is the same steps.

So:
f(N)=2*f(N-1) + 1

The recursion ends when f(1) = 1 (one step to move one peg).
One now can easily reduce the counts by finitely recurse until f(1), which is, if we write it as sum of power of two, is the same as writing binary in this form:
f(N) = 2^N – 1 –> which is basically all 1 in binary until N digits.
So, for 2 pegs, it is like: 11 in binary (2 digit).
3 pegs becomes: 111 in binary (3 digits).
and so on.
It's just because: 2^3+2^2+2^1+1 is equivalent to 1111 in binary for 4 pegs.
Amazing.

Sier-π-nski?

#### Ryan · December 24, 2018 at 4:42 pm

Did You Know That Hanoi Is A Real Place : https://drive.google.com/open?id=10m0h945b31w-xIP5U9TGN7iLYXFQrP_s&usp=sharing

#### Andres Zeballos · December 27, 2018 at 9:47 pm

I'm going to try it with my child, love the way to correlate to binary with hanoi towers, and the recursive approach

#### Sunny K · January 5, 2019 at 3:27 pm

5:46
this is when i got what 3b1b was saying: i made a cpde that prints out the stepbystep solving of hanoi that prints out
A C
A B
C B

where A C means move the top one in A to C. i used recalling?(재귀) functions for it: hanoi repeats itself. for blocks in A, move all but the last one to B, move the last one to C, move everything in B to C. how do i move everything except the alst from A to B and B to C? recall that function. all that the function does is move blocks from one place to another. why did i get hanoi=bi in 5:46 ?
<hanoi:moving blocks from A to C>
1.move all-1 from A to B
2.move one to C
3.move all to C(which is the same as step 1)
<binary counting>
1.increment all-1 so all digits are 1
3.increment again(which is the same as step 1)
a programmer's explanation on why this work. 3b1b you and your friend is a genius!

#### True River · January 7, 2019 at 11:04 am

This is overly complicated if the aim is to solve Hanoi. The shortest algorithm is as follows

1. First move: only legal moves involve moving the smallest. If there's an odd number of disks move the smallest to the destination; if even move smallest to the other peg. Note which direction it moved.

2. On even numbered moves make the only move available move that leaves the smallest where it was

3. On odd moves move the smallest in the same direction as step 1.

That's it!

You do not need the rest of the binary number, just the last digit. In effect you only need odd-even so a simple toggle is enough, adding in modulo 2.

And when adding mod 2, the numbers look the same in any base: 1 0 1 0 …

Binary is a distraction: it's mod 2 that matters

#### youra ramuser · January 11, 2019 at 7:23 pm

EXTREME SIMPLIFICATION!!

#### Fort-newton · January 15, 2019 at 9:36 pm

Ur wrong moving disk 3 to the C peg is redundant I think if I’m wrong please let me know

#### Calo Zheng · January 16, 2019 at 11:56 am

Love the smooth animation.

#### Kelvyn Brito · January 17, 2019 at 8:02 pm

Very cool! Great explanation!

#### lapidations · January 19, 2019 at 3:20 am

Starting at 8:18, when we're seeing what disk 3 is thinking, the "3" looks like its kissing lips, like "°3°", you know?

#### Nicod3m0 Otimsis · January 21, 2019 at 11:52 pm

I know no one cares about a comment in a years-old video, but I think that there is a (for the sake of video editing length, I understand, it is okay) left out topic. In the recursion you propose, you establish that the disk 0 should always flip to the right, and go modular once it reaches the edge, I mean, do module 3 so you return to the tower 0. So, why? And I think this is not a naive question, well, it is, until you consider the next. As it is obvious, you show a lot of examples, animated, so I could pick out a simple pattern. A) you don't care where the tower is newly created B) following your "algorithm", the towers en up solved in different towers C) the tower they finish on is related to the parity, no big deal. But, casually, the parity (I mean if it is an odd or pair number of disks) is very closely related to the last bit in binary, precisely the bit you decided to have an arbitrary behaviour. So my best guess is that because of how you established the recursion, and how you treat the last bit, or in other words, because how you decided to move the ring 0, your towers get solved in a different place. Now the obvious question, can anyone please shut up my pretentious intuition by explaining the rational math behind this so that I can stop thinking about a stupid game and go back to doing hi and elevated maths. (take the last part with some irony)

#### Rachel Davies · January 29, 2019 at 2:56 am

Sierpinksi’s triangle? More like complicated triforce.

#### Rachel Davies · January 29, 2019 at 3:00 am

Is it really the most efficient solution it seems like you would never have to move the largest disc until the one where you move it to the center.

#### Carter Tangeman · February 1, 2019 at 6:51 am

"The most efficient way possible"
7:58
Moves largest disc unnecessarily, changing nothing.

#### Nelyon Quenya · February 5, 2019 at 3:11 pm

What if you add another stick does it go to base 4?

#### Trevor MacIntosh · February 17, 2019 at 5:01 am

Honestly, these two videos are my favourites of yours. I’ve rewatched them so many times. SO COOL.

1) very fast

#### Piotr Masłowski · February 17, 2019 at 12:02 pm

I've just realised how funny is the way the whole world pronounces Sierpiński's surname.

#### Matthew H · March 3, 2019 at 10:34 pm

1:45. There are also Tower of Hanoi apps that let you try out the puzzle by hand.

bits
tets
QUIT s
fifs
sexes
sets
octs
nots
dets

#### Cheeseburger Monkey · March 21, 2019 at 12:12 pm

6:09 I DIDNT KNOW YOU OVED EXACTLY 1 DISK PER SECOND!?

#### Bernat Ibáñez · March 23, 2019 at 10:20 pm

When I started doing python I made a script to solve the Hanoi towers, but I didn't know what recursion was so I analyzed different cases and found a really weird relationship between numbers and letters. I thought about recursivity as you mention it here, but I solved it completely different for n disks with the most efficient moves. I could show you the code, but it is very messy and I, to this day, still not understand how the math I did really works xDD

Heck yeah!

#### GNM · April 3, 2019 at 8:18 pm

5:47
salutes in pannenkoek

#### Lupine Dream · April 4, 2019 at 4:44 pm

Could you count down with an inverse of the rules to say, reverse a set of data in the most efficient way ? Lets say you wanted to stack them upside down on the third stack, or by the median ?

I have so many questions :v

#### hoang anh vuong · April 7, 2019 at 5:54 pm

I just played with that since I was a kid(I love math). i've found the pattern, calculated the number of moves. But I didn't know why that's works. Until I saw this video.
And I was like: "wow, this is truly fascinating" (btw, I'm really proud that the puzzle's name Hanoi is our capital)

#### Salim Huerta · April 10, 2019 at 4:12 pm

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.

#### Salim Huerta · April 10, 2019 at 4:13 pm

My favorite thing for drives home from work

#### Jackie Lin · April 12, 2019 at 7:57 pm

https://hanoi-animation–p3artschool.repl.co/

[Tower of Hanoi animation]

tools: repl.it web python 3.6 + svgwrite 1.2

file format: HTML5 svg

#### Patriot · April 13, 2019 at 7:12 am

This works and i have solved this some years ago on a similar way; by odd and even numbers which when you turn in binary is numbers ending in 1(odd) and numbers ending in 0 (even)

#### Jeff Carroll · April 17, 2019 at 5:20 am

Also, if you count the starting position as 1, then the least number of moves to solve the puzzle with n disks will always be 2 to the nth power. 1 disk = 2 moves, 2 disks = 4, 3 disks = 8, 16, 32, 64, 128, 256, etc… Solution is always a power of 2.

#### Gameeustrupter · April 17, 2019 at 9:20 pm

Every once in a while I have to watch one of these twice, mabey because I'm in middle school though

#### Venom Supreme · April 21, 2019 at 2:18 pm

Isn’t it also the only way to solve it without reversing logic? Therefore any other solution I believe would contain redundancies.

bin(3) =11
bin(7) = 111
numbin(101) = 5

#### Sean · April 24, 2019 at 1:55 am

I somehow did come here without watching the other video

8:18
(0 3 0)

#### Rajat Prakash · May 7, 2019 at 6:10 am

I loved it. Thanks.

#### OlPa · May 24, 2019 at 5:01 pm

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!

#### D&Darkrai · May 29, 2019 at 12:00 am

Love towers of hanoi, and there many patterns. Youll move a peice on spot over twice then two spots once then 1 spot twice etc. you also move discs in order: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 etc. lastly if u notate your moves as ring moved in first place then left or right then how many spots (5R1 would be fifth ring right one slot) your full notation for an n solve will always be palindromic

#### f96 · June 2, 2019 at 11:47 am

call them tets lmao

#### david ortega · June 23, 2019 at 6:45 pm

this guy is the same from majorprep?

#### Cheydinal · July 2, 2019 at 1:01 pm

In binary, "base 2" is written as "base 10"

#### Random Dude · July 16, 2019 at 3:03 pm

I had to slow down that procedure part at 6:18 just to understand how it works. And it's mind blowing!

#### Gregory Fenn · July 28, 2019 at 9:58 am

The audio from your guest speaker is really poor quality, it actually bored me because it reminded me of those terrible VHS science videos your teacher made you watch on rainy days (the content of what he says is fascinating, but the poor audio triggers some kind of Pavlovian reflex that makes me want to think about anything else).

Now this game isn't funny anymore because I don't have to think to solve it, thanks, I hate it x)

#### Eric Jin · August 2, 2019 at 12:52 pm

Ohhhhhhhhhhh python XD
BTW, your function at 10:00 will break down at 1000, unless you “sys.setrecursionlimit(2147483647)''

#### Syaoran Code · August 3, 2019 at 6:13 am

that's so cool, now I can solve it even many disks

#### Mgtow Values · August 4, 2019 at 8:54 pm

The problem with all teleological explanations is one must arrive and look back and then say hey "we were always headed towards here". Occasionally, people do this in their minds.

#### John Brocksman · August 9, 2019 at 4:51 pm

Fuck I spent the last 30min using 6 blocks and I just realized I only needed 5, I solved 5 in like 10 minutes fml

#### Wa55abi · August 10, 2019 at 11:37 am

The colours of the binary digits are in opposite direction to the disc colours 🙂 Never the less, great video!

#### Kaczankuku · August 11, 2019 at 2:39 pm

You deal with Sierpiński triangle a long time so you finally should learn how to correct pronounce his name. I hear still the same your anglosaxon "r" and you miss the initial sound so called in Polish soft "s".
https://en.wikipedia.org/wiki/Wac%C5%82aw_Sierpi%C5%84ski – check this out.

#### Proxy · August 14, 2019 at 11:33 am

4:10 but why reist? it is 10… just in base2.
the defintion of what 10 is is based on the base used, but it can still be called ten and be correct. so a 10 in octal is completely different than a 10 in hexadecimal for example. but they are still called the same.

#### Rask R · August 15, 2019 at 6:51 pm

Is this even considered a puzzle? You just need to do first legal move available without repeating positions and that's it. No thinking at all

#### Tyom Sahakyan · August 16, 2019 at 12:36 pm

do the same with 3 discs 🙅🏻‍♂️

#### TinyFoxTom · August 19, 2019 at 3:57 pm

I came across this pattern frequently (no pun intended) while creating a computer in Minecraft. When laying down wire for 2^(n+1) addresses, the 1's place in the address looks like a sine wave of frequency f, the 2's place has a frequency of f/2, and the 2^n's place has a frequency of 2^-n*f. I never thought to apply it to the Towers of Hanoi, though. It also shows up in the rules of cellular automata. Minecraft is technically a cellular automata, but the address pattern wasn't dependent on that fact.

#### Anthony Nguyen · August 20, 2019 at 1:48 pm

realizes I could solve tower of Hanoi when I was younger and realizes I might not be a genius

Towers of Hanoi!

#### bauagan · August 31, 2019 at 12:28 am

If I didn't grow up with so called western world numbers, I'd find this video severely informative ;D I love this planet ;D

#### Nguyen Chester · August 31, 2019 at 5:50 am

what does this have to do with Hanoi?

#### Antonio Sraffa · September 2, 2019 at 7:52 pm

Visual example of backwards induction, its ties to mathematical induction, and showing off the use for binary to manipulate two-state models…and none of that was even center-stage in this (or the next) video.

We are not worthy!!!!

τ⚔π

#### Ben D. Manevitz · September 6, 2019 at 4:48 pm

Minor quibble – you should be more clear that the rule for flipping the 2^0 bit is different than all the other bits. The 2^0 bit moves — naming the posts 0-1-2 left-to-right — in a (+1 mod 3) pattern, while the other bits go to "whichever one they can without breaking the other rules of the game."

The rule itself is necessary because unlike the other bits the 2^0 bit has choices. For instance, when you're going from 011 to 100, the 2^0 bit could go on top of either post 0 or 2. Putting it on post 2 is correct move, but putting it on post 0 doesn't violate any rule of the game.

The clarification may not be necessary, per se. But I missed it when I was watching the video and I'm feeling pedantic.

#### Ben D. Manevitz · September 6, 2019 at 4:50 pm

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…

#### Sumit Aggarwal · September 7, 2019 at 7:51 am

is it only applicable for 3 pegs?

#### Alex Loomis · September 10, 2019 at 4:43 am

Woooaaahhh fine structure constant easter egg

informative

#### Don't Sub Me · September 22, 2019 at 5:40 pm

This puzzle is extremely easy equalent to finding the guarenteed winning/draw pattern in tic tac toe

#### Victor Barroso · October 11, 2019 at 7:10 pm

Once you see disk 3 sending you a kiss, you cannot unsee it

#### TimmyLP · October 15, 2019 at 6:47 pm

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.

#### TheSpaceMan88 p · October 15, 2019 at 6:57 pm

you've done a little error at 5:59 11111111 in binary equals to 256 not 255 (which is 11111110 in binary) cause 2**8 = 256 otherwise realy nice video keep going like this (sorry for grammar error )

lo

#### nj foever niso · October 22, 2019 at 5:32 am

Pop😛😚🤣😭🙋💆🤸🤹🤼🏄🏂⛷️🏇🎅🤶🧚🦸🧟👰👸🤴🤶

#### Jowat · October 22, 2019 at 11:26 am

OK… I'm sorry for seeing this video this late but…

the first thing I asked myself is "where do you move it" and actually
if it's a even disk, move it to the right
if it's a odd disk, move it to the left

I had to comment my observation…

#### The MinecraftR 9598 · October 31, 2019 at 5:14 am

7:14 Are you certain it’s always the most efficient? Moving the 3 seems like an extra step.

24

#### Nick van Schoonhoven · November 23, 2019 at 12:51 am

Is there an algorithm that would tell us how many fewer moves would be required if we were to add additional pegs?

#### Justin Moore · December 2, 2019 at 1:50 pm

Time to go back to doing what I was programmed to do. That's to bust out of constructs.

#### torix · December 13, 2019 at 2:32 am

why does keith sound identical to zillion ross

#### Tom Kanazaki · December 21, 2019 at 2:33 am

Vietnamese Hanoi puzzle?

dank as always 😉

#### J M Roblox · January 4, 2020 at 4:23 am

There are 10 Types Of People In The World:
People That Understand Binary,
People who don't,
People that thought this joke is Binary

And

People that thought this joke is ternary.

#### 김재원 · January 12, 2020 at 12:32 pm

And you just became my favorite youtuber

#### Zachary Allen · January 18, 2020 at 4:02 pm

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.

#### GG Entertainment · January 22, 2020 at 11:57 am

does it also work with more than 3 pegs?

#### los zdog · February 17, 2020 at 5:24 pm

There are 10 types of people: those who understand binary, those who don’t, and those who weren’t expecting a ternary joke

#### Brian Clarke · February 22, 2020 at 3:11 am

Rare natural occurances. Makes me think about the creation of the universe

#### Jared Oz · February 25, 2020 at 1:33 pm

This is EXACTLY why I'm not teaching anymore. I couldn't explain it better. Thank you.