The Towers of Hanoi

[WhiteCube]

Recently there was a post about the brute force method. The thread was deleted for some reason, but it did contain an interesting conjecture about the Towers of Hanoi.

I will restate it here, this is not my idea.

The list of the pegs used in the recursive solution, has a simple pattern, and so a non recursive program is easy to make.

12 13 23 12 13 23 ...

It is easy to test (for small cases, up to 16 discs) but I'm having trouble proving it for all cases.

Any ideas?

The reason I think this idea has merit is because if someone challenged me to solve the towers with 5 discs, I would have tried to apply the usual algorithm, lost track of the stack, and failed to solve a child's toy.

 

[Chaos]

The Towers of Hanoi is a classic problem in computer science and mathematics that involves moving a tower of disks from one peg to another, subject to the constraint that only one disk can be moved at a time, and no disk can be placed on top of a smaller disk.
The recursive solution to the Towers of Hanoi involves moving the tower of �n disks from the source peg (let's call it �A) to the destination peg (let's call it �C) using the auxiliary peg (let's call it �B).
The recursive algorithm can be expressed as follows:

1. Move �−1n−1 disks from �A to �B.
2. Move the ��ℎnth disk from �A to �C.
3. Move the �−1n−1 disks from �B to �C.

This recursive process is then applied to the subproblems until the base case of �=1n=1 is reached.
Now, regarding the pattern you mentioned: 12,13,23,12,13,23,…12,13,23,12,13,23,…, it seems like you're observing the sequence of pegs used during the recursive steps. This pattern is related to the choice of pegs for each move in the Towers of Hanoi. The pegs are labeled 11, 22, and 33, corresponding to �A, �B, and �C respectively.
You mentioned that the pattern is easy to test for small cases. To prove this pattern for all cases, you could use mathematical induction. The base case is �=1n=1, where the sequence would be simply 1212. Then, assuming the pattern holds for �−1n−1, you can show that it holds for �n as well.
In general, mathematical induction is a powerful tool for proving patterns in recursively defined sequences or functions. If you're having trouble proving it, you may want to break down the proof into smaller steps and ensure that each step is logically sound.
Remember that the Towers of Hanoi is known for its elegant recursive solution, and it's always interesting to explore different ways of understanding and expressing its patterns.

 

[alexcray]

Recently there was a post about the brute force method. The thread was deleted for some reason, but it did contain an interesting conjecture about the Towers of Hanoi.

I will restate it here, this is not my idea.

The list of the pegs used in the recursive solution, has a simple pattern, and so a non recursive program is easy to make.

12 13 23 12 13 23 ...

It is easy to test (for small cases, up to 16 discs) but I'm having trouble proving it for all cases.

Any ideas?

The reason I think this idea has merit is because if someone challenged me to solve the towers with 5 discs, I would have tried to apply the usual algorithm, lost track of the stack, and failed to solve a child's toy.

Proving the pattern directly for all cases could involve analyzing the underlying logic of the Towers of Hanoi solution and demonstrating how it leads to this specific repeating sequence. This might require advanced combinatorial reasoning.

 

[WhiteCube]

The inductive proof is complete.

Its not pretty. I won't post it, because it may contain mistakes.