Proof of Iterative Solution for Tower of Hanoi Problem

combinatorial-game-theorypuzzle

So I was exploring the Towers of Hanoi problem on wikipedia, and I came across the iterative solution of:

  1. Make the legal move between pegs A and B (in either direction)
  2. Make the legal move between pegs A and C (in either direction),
  3. Make the legal move between pegs B and C (in either direction), repeat until complete

for an even number of disks, and for an odd number of disks:

  1. Make the legal move between pegs A and C (in either direction)
  2. Make the legal move between pegs A and B (in either direction),
  3. Make the legal move between pegs B and C (in either direction), repeat until complete.

Why does this iterative solution work? I explored a bit further and discovered that if you continue this set of instructions even when the disks are all on the right pole, the disks will eventually end up in a pile in the middle pole. Why does this happen?

Best Answer

If you're interested, I explain how to solve the Tower of Hanoi (plus induction proofs) in this video.

The Iterative Solution basically relies on the principle of induction. If you know how to move a tower with $n-1$ pieces then you can figure out how to move a tower with $n$ pieces. The solution is basically

  1. Move $n-1$ pieces from pole A to pole C
  2. Move the remaining disk on pole A to pole B
  3. Move the $n-1$ tower you left on pole C back on top of pole B

Of course step 1) is much more involved than the other steps! Let's unroll step 1) and see what patterns we notice.

  1. Move the $n-2$ pieces from pole A to pole B
  2. Move the $n-1$ disk that's left on pole A to pole C
  3. Move the $n-2$ tower from pole B onto pole C
  4. Move the remaining disk on pole A to pole B
  5. Move the $n-1$ tower you left on pole C back on top of pole B

Aside from step 1), the other steps involve moving a single disk (the only legal move) at a time between the poles in a pattern indicated by the iterative solution. This pattern is $$ A\rightarrow B\\ A\rightarrow C\\ B\rightarrow C\\ A\rightarrow B\\ C\rightarrow A\\ C\rightarrow B $$

If we completely unroll step 1), then we see that the full move sequence for solving the Towers of Hanoi is just repeating this pattern of $6$ steps over and over until we are done. Of course, if we want the tower to end up on a specific pole, we may have to reorder the $6$ steps depending on if the initial tower has an even or an odd number of disks.

Related Question