2
$\begingroup$

The problem of Tower of Hanoi is a typical example of recursion method. Could anyone show me the (simple) proof of

(1) the smallest number of moves of the solution is 2^n-1

(2) the uniqeness of the optimal solution (the solution with the smallest number of moves)

(I found (1) in the Concrete Math of Knuth, is there any other proof ?)

$\endgroup$
4
$\begingroup$

Without knowing the proof you mention or being very formal, I'd go for the combined one below.

With induction: For the case $n=1$, it is easy to see that you need at least one step to do anything and if you enumerate the possible steps you'll get that there is precisely one step that moves the tower to the right place.

For the case $n=m+1$, for some $m\ge 1$, looking at the bottom stone it is clear that it can only be moved after all others are moved elsewhere first. To move the bottom stone there are two options, one of which puts it where it needs to be in the end, but in both cases it can only move if the target "site" is empty. This leaves only one place for all the other stones to be, and by the rules of the game they have to be in order and thus form a tower. This means the top has to be moved as a whole from one place to another. So in both cases the smallest number of moves is the smallest number of moves to move the top (of size $m$) completely, which is $2^m-1$ and unique by induction, plus $1$ for the bottom stone, giving $2^m$ so far.

Now we are left with two cases. For the one where the bottom stone is already in place, we have a tower of size m elsewhere that needs to be moved on top of it. Moving the bottom stone itself either gives use a previous state or the same state as the following case and these paths can therefore not be minimal. To move the top we know, again by induction, that the smallest number of moves is $2^m-1$ and that the moves are unique. The total number of moves in this case therefore is $2^m+2^m-1=2^{(m+1)}-1=2^n-1$.

In the other case we know that we still have to move the bottom stone to the right place and in fact we can easily see that the current case is effectively the same as the situation before the bottom stone was moved there (but after the top was moved). The last move being superfluous means this path cannot lead to a minimal number of moves. This leaves the previous case as the only suitable case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy