Post #3917451

Why do paths through the nth approximation to the Sierpiński triangle correspond to allowed sequences of moves in the n-disc Tower of Hanoi? Well, suppose you have 3 discs. Draw the allowed states of the Tower of Hanoi puzzle as below. For example, (3,2,1) means "biggest disc on post 1, second biggest on post 2, third biggest on post 3". Draw edges for allowed moves between states. You get the 3rd approximation to the Sierpiński triangle! I got this picture from an article with more details: • Alexander Bogomolny, Sierpinski Gasket and Tower of Hanoi, https://www.cut-the-knot.org/triangle/Hanoi.shtml