2
$\begingroup$

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows.

Hanoi(n, src, dst, tmp):
  if n > 0
    hanoi(n-1, src, dst, tmp)
    move disk n from src to dst
    hanoi(n-1, tmp, dst, src)

And iteratively,

If n is even, swap pegs 1 and 2. At the ith step, make the only legal move that avoids peg i mod 3. If there is no legal move, then all disks are on peg i mod 3, and the puzzle is solved.

 hanoi(n, s, t, d)
  pegs[s = [1,2,..,n], t, d]
  if n is even
    swap pegs[1], pegs[2]
  i <- 1
  while(pegs[d].length < n.length)
    avoid <- i mod 3
    if the top of pegs[(avoid + 1) mod 3] > the top of pegs[(avoid + 2) mod 3]
      move the top of pegs[(avoid + 1) mod 3] to pegs[(avoid + 2) mod 3]
    else
      move the top of pegs[(avoid + 2) mod 3] to pegs[(avoid + 1) mod 3]
    i++

I'm having a hard time figuring out how to put this into mathematical expressions or a recurrence-relation which I can then perform induction on to show their equivalence.

My searching has only brought me problems that deal with the complexity or correctness of algorithms, I'm interested in showing that every $i$th move the performed are identical.

$\endgroup$
  • $\begingroup$ Are you sure the conclusion is correct? For example, is the case of n=3 correct? How do you convince yourself? $\endgroup$ – Apass.Jack Jan 18 at 1:12
  • $\begingroup$ Sorry, I mixed up the move commands in the iterative version, they should be the other way around. It's been given that the algo's are equivalent, even though I might botch the translation to pseudocode. But that isn't what I'm worried about at the moment, I just can't figure out how I set this up for induction, what the equivalence that I'm trying to prove actually looks like, even if I was given the correct pseudocode I don't know where to take it from there. $\endgroup$ – gunnnnii Jan 18 at 10:42
  • $\begingroup$ You have a mistake in your recursive procedure. Can you find it? $\endgroup$ – Yuval Filmus Jan 18 at 12:26
  • $\begingroup$ A good first step is to formulate what you're trying to inductively prove. $\endgroup$ – Yuval Filmus Jan 18 at 12:27
2
$\begingroup$

Let's start with reformulating the two solutions, following Wikipedia. We use A for the source peg, B for the auxiliary peg, and C for the destination peg.

Recursive algorithm

  1. If $n > 1$, recursively move $n-1$ discs from A to B.
  2. Move the $n$th disk from A to C.
  3. If $n > 1$, recursively move $n-1$ discs from B to C.

Iterative algorithm

If $n$ is even, execute repeatedly until done:

  1. Make a legal move between A and B.
  2. Make a legal move between A and C.
  3. Make a legal move between B and C.

If $n$ is odd, execute repeatedly until done:

  1. Make a legal move between A and C.
  2. Make a legal move between A and B.
  3. Make a legal move between B and C.

(We terminate the algorithms whenever there is no legal move.)


We will prove that both algorithms coincide, using the fact that the recursive algorithm makes exactly $2^n-1$ moves, which can easily be proved by induction. The base case is $n = 1$. In this case, the recursive algorithm moves the disk from A to C, and this is also what the iterative algorithm does.

Suppose now that we have proved the claim for $n$. We will prove it for $n+1$. There are two cases to consider, according to the parity of $n$. Suppose first that $n$ is odd.

The first step in the recursive algorithm is to move $n$ discs from A to B. We know that this is the same as running $2^n-1$ steps of the iterative algorithm for odd many disks, with B and C switched. We observe that upon switching B and C, we exactly obtain the iterative algorithm for even many disks. Therefore the first $2^n-1$ moves made by the iterative algorithm coincide with what the recursive algorithm does (this is because at any step there is a move involving one of the first $n$ disks).

Since $2^n-1 \equiv (-1)^n-1 \equiv 1 \pmod{3}$, after executing $2^n-1$ steps, the next step in the iterative algorithm is to make a legal move between A and C, which is exactly what the recursive algorithm does. We can now rephrase the remaining operation of the iterative algorithm as repeatedly executing the following moves:

  1. Make a legal move between B and C.
  2. Make a legal move between A and B.
  3. Make a legal move between A and C.

This is exactly what the iterative algorithm for odd many disks looks like after switching A and B. Therefore just as before, the following $2^n-1$ steps of both algorithms coincide. The same calculation as before shows that the next move to be considered in the iterative algorithm is the one involving A and B, but there are no disks on either of these pegs, so the iterative algorithm stops. This completes the proof for odd $n$.

The proof for even $n$ is very similar. The first $2^n-1$ moves coincide since switching B and C switches the two versions of the iterative algorithm. This time $2^n-1 \equiv 0 \pmod{3}$, so the next move to be considered by the iterative algorithm involves A and C, matching the recursive algorithm. We can rephrase the operation of the iterative algorithm henceforward as repeatedly executing

  1. Make a legal move between A and B.
  2. Make a legal move between B and C.
  3. Make a legal move between A and C.

This is the same as the iterative algorithm for even number of disks with A and B switched, so the following $2^n-1$ moves coincide. The next move to be considered again involves A and B, which is impossible. This completes the proof.

$\endgroup$
  • $\begingroup$ Thank you very much! My problem was exactly formulating my arguments, this is very helpful! $\endgroup$ – gunnnnii Jan 18 at 17:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.