Reverse Puzzling 2

Question

This puzzle was inspired by Dr Xorile's first reverse puzzle! Kudos to him for coming up with such a fun format.

Intrigued, I gave George yet another famous puzzle to ponder over. Once again, I was surprised that he had not seen this before either.

George frowned, paused for a few moments, and then picked up his trusty marker and started drawing a diagram.

My eyes widened in horror as I realized that George would take a long time if he kept up this strategy. I didn't have time for him to complete his diagram.

"Wait, George! Let's... let's try an easier version of the same puzzle. A much easier version."

I gave George the revised puzzle and he eventually came up with the following diagram for it.

"Ah! The answer is obvious now!" George exclaimed. I eyed George warily. I was starting to think he was more of a 'tedious' puzzler than a 'great' one.

What was/were the puzzle(s)?

Answer 1

This puzzle is the Towers of Hanoi with three disks. A, B, and C are the pegs, and the positions from left to right are the disks; the lines connect positions that are valid to move between.

The initial puzzle is probably the Towers of Hanoi with more disks - the area needed to draw the diagram is quadrupled with every new disk added, so a larger diagram would take up much more space and time.

Answer 2

Just to expand on @Deusovi's devious answer, you can convert the states described in the circle to a game state as follows:

1. Start with a set of empty pegs, labelled A, B, and C.
2. Place the biggest disk on the peg with the letter shown on the right.
3. Place the middle disk on the peg with the letter shown in the middle.
4. Place the smallest disk on the peg with the letter shown on the left.

Note that by doing this in this order, there are no problematic states - every peg is available for every disk. The is also how you can see that there are $3^n$ states when there are $n$ disks.

Now you could just write all these $3^n$ states out and join them up, but you'll note that @AZGreenTea did it in a very symmetric way. You can see that the triangle is made up of three smaller triangles, each of which has the same right hand letter = biggest disk. There are a limited number of ways to move the biggest disk (basically when everything else is piled up on a different column), so the triangle you see can be replicated three times, adding a forth letter (A, B, and C). These can also only be joined in the corner, and so the triangles you see are replicated three times and put into a bigger triangle for $n=4$.

This self replication is, of course, fractal in nature, and hence the link between the towers of Hanoi and the fractal in question, which turns out to be Sierpinski's triangle.