💾 Archived View for tilde.team › ~smokey › fractal_compendium › sirpin › towers-of-hanoi.gmi captured on 2023-01-29 at 04:15:28. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
imagine you have three poles horizontal to one another and label them A, B, and C respectively.
| | |
| | |
| | |
A B C
Now, We have three different size circular disc with a hole in the center to slide onto the pole. Just like doughnuts!
.-" "-.
.' . ; `.
/ : . ' : \
| ` .-. . ' |
| : ( ) ; ` |
| : `-' : |
\ .` ; : /
`. . ' .'
`-.___.-'
Stack them on any pole you would like, I chose A for this example. They MUST be stacked largest on bottom, smallest on top. You ARE NOT allowed to put a larger disc on top of a smaller disc at any point.
Move 0:
[1] | |
[_2_] | |
[__3__] | |
A B C
The goal is to move all the disc one step at a time from the starting pole to any either of the other given the rules.
I encourage you to try out the puzzle yourself, find 3 different size books and stack them on eachother and see if you can solve the puzzle.
Move 1:
| | |
[_2_] | |
[__3__] [1] |
A B C
Move 2:
| | |
| | |
[__3__] [1] [_2_]
A B C
move 3:
| | |
[1] | |
[__3__] | [_2_]
A B C
move 4:
| | |
| | [1]
[__3__] | [_2_]
A B C
And so on.
I recommend watching 3B1B's two part video series "Binary, Hanoi, and Sierpinski part 1 & 2". He explains it far better than i probably can, with fancy animations to boot.
Part 2, The visualizations we are interested in for this section are 7:41
When we consider the supergraph of all possible positions, as well as how those positions are connected, A familiar structure begins to emerge.
Move 1, move 2 and move 3 are all examples of different positions you can arrange the disc. But how many different positions are there exactly? The answer depends on the amount of disc you have to play with, but in the case of 3 disc its 27. 27 possible arrangements of disc positions.
Is there a way that we can graph these different arangements so that we can see the relationship of how one position goes to the next? Yes!
To start off, draw three bubbles in a triangle-ish arangement. inside these bubbles will be each particular arrangement of disc.
In the bottom left bubble, draw move 0, all disc on A. Next, consider the two next legal moves we could take given the rules. At the start, we had the option of moving disc 1 to either B or C.
So, draw the arrangement with disc 1 on B in the upper bubble and on C in the lower right.
Draw a line connecting the bubbles if you can go across positions in a single valid move.
After that, its a matter of drawing all 27 bubbles and connecting them in this arrangement:
all disc on B --> []
/ \
[]----[]
/ \
[] []
/ \ / \
[]--[]----[]----[]
/ \
move 4 -> [] []
/ \ / \
move 2 -> []--[] <- move 3 []----[]
/ \ / \
move 1 -> [] [] [] []
/ \ / \ / \ / \
All disc on A -> []---[]---[]---[]----[]--[]---[]---[] <-- All disc on C
(move 0)
Hello sierpinski my old friend!
As we increase the number of disc, the graph becomes higher iterations of the sierpinski triangle.
As it turns out, theres also a path that walks through every position once and only once. this path is the sierpinski arrowhead curve.
_
/ \
\ /
_/ \_
/ \
\_ _/
_ \ / _
/ \_/ \_/ \
\ /
_/ \_
/ _ _ \
\_/ \ / \_/
_ / \ _
/ \ \_ _/ / \
\ / _ \ / _ \ /
_/ \_/ \_/ \_/ \_/ \_
/ \
\_ _/
_ \ / _
/ \_/ \_/ \
\ _ _ /
_/ / \ / \ \_
/ _ \ / \ / _ \
\_/ \_/ \_ _/ \_/ \_/
_ \ / _
/ \ _/ \_ / \
\ / / _ _ \ \ /
_/ \_ \_/ \ / \_/ _/ \_
/ \ _ / \ _ / \
\_ _/ / \ \_ _/ / \ \_ _/
_ \ / _ \ / _ \ / _ \ / _ \ / _
/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \