How to prove the optimal Towers of Hanoi strategy?
In the towers of Hanoi game, how do we know that we have the optimal algorithm for solving it? I thought about this and it seemed like any deviation from the standard strategies would be putting you back a step, but I had no idea how to demonstrate this rigorously.
All I know is that the proof involves the Lucas correspondence between the Hanoi graph and the odd coefficients in Pascal's triangle. How is Pascal's triangle turned into a graph? I assume the coefficient are the vertices, but I don't see how you form the edges?
I was also wondering how to generalize the strategy to n discs and k rods because it seems like this correspondence argument wouldn't really work in the general case.
Basically, I am wondering how the odd coefficients of the Pascal triangle are turned into a graph and whether or not there is a similar method to find and prove optimal strategy when we increase the number of rods.
I will address your first question, but not the one for larger number of rods; as far as I know, it's still generally wide open what the optimal strategy might be even for $4$ rods and a smallish number of disks.
To show the optimal strategy for $n$ disks in $3$ rods is the "usual" one, you can do it by induction (which yields a recursive solution). I'm sure there are other ways of proving it, perhaps with Lucas numbers as you suggest.
Clearly, the optimal strategy with $n=1$ is to simply move the disk directly.
Assume you already have the optimal strategy for moving $k$ disks. To move $k+1$ disks, you need to move the largest disk from the initial rod to the terminal rod, but that is the only time it needs to move (it cannot help you with the other disks, since it must lie at the bottom at any given time, so any other moves only require further moves in the end); to move the bottom ($k+1$)st disk from the initial rod $I$ to the terminal rod $T$, you must first move the top $k$ disks out of the way; this requires moving the $k$ disks from the initial rod $I$ to the auxiliary rod $A$, and the optimal way of doing this is the optimal strategy you know for $k$ disks. Then you move the $k+1$st disk, and then you want to move the remaining $k$ disks from the auxiliary rod to the terminal one in as few moves as possible (the optimal way). So the optimal strategy for $k+1$ disks is to move the top $k$ using the optimal strategy for $k$ from $I$ to $A$, then move the largest disk from $I$ to $T$, then move the top $k$ disks using the optimal strategy for $k$ from $A$ to $T$.
By keeping track of the actual number of moves needed at each step, you can give the number. For $n=1$, the number is $1=2^1-1$. Assume that moving $k$ disks requires $2^k-1$ moves in the optimal strategy. The optimal strategy for $k+1$ described above takes $(2^k-1) + 1 + (2^k-1) = 2^k+2^k - 1 = 2^{k+1}-1$ steps; thus, the optimal solution for $n$ disks and $3$ rods requires $2^n-1$ moves.
(This does not generalize easily to more than $3$ rods for presumably obvious reasons).
A bit more interesting is trying to prove that the non-recursive solution gives an optimal solution; this solution only requires you to remember the last disk you moved at any given time (the recursive solution is more memory intensive, of course). Number the rods $0$, $1$, and $2$. We have three rules:
- Never move the same disk twice in succession.
- You can only move a disk from the top of one rod to the top of another rod.
- Moving a disk from rod $i$ to rod $j$ is only valid if $i\neq j$, and either rod $j$ is empty or the top disk in rod $j$ is larger than the top disk in rod $i$.
With these rules, the non-recursive algorithm has two simple steps:
- If you are moving the disk from rod $i$, and the two other rods are valid destinations, then move it to rod $i+1\mod 3$. Otherwise, move it to the only valid destination.
- If no move is possible, stop. Otherwise, continue.
This process will solve the puzzle with $3$ rods in the minimum number of moves.
In general, with n rods and n disks, the problem is equivalent to finding a Hamiltonian path on an n-hypercube. There is no proven optimal strategy known for 4 rods. You could also read the MathWorld article which has references for quite a few papers on the subject.