Question

Here's a fun problem for people learning induction.

Consider the problem of solving the problem of the Towers of Hanoi with n disks (see, for example, the wikipedia article).

Prove by induction that
a) the number of states of the system is 3^n
b) that any state can be reached from any other state by a finite number of legal moves
c) that the number of moves for the optimal solution is 2^n - 1

Answer 1

Originally posted by JamesJ in the generic math section.

Answer 2

Here's a slightly long but careful answer to part b. This is the sort of thing I'd expect from a first year university student:

Let's consider the general case with n disks and 3 tower pegs, and let P(n) be the statement "Any state of the n disks on the three tower pegs may be reached from another by a finite set of legal moves."

Clearly P(1) is true, as we may move any one disk from one peg to another.

Now let's show that P(k) implies P(k+1) for an arbitrary positive integer k.

Some notation will be helpful. Write t(d) as the tower peg on which disk number d is located; t then a function {1,2, ..., n} --> {1,2,3}.

A state of the system them is a function t. Let t0 correspond to the state where all the disks are on the leftmost peg: t0(1) = t0(2) = ... = t0(n) = 1.

We will say that another state t is equivalent to t0 if it can be reached in a finite number of legal moves; let's write t0 ~ t. It's not hard to convince yourself that ~ is an equivalence relationship and if t0 ~ t1 and t0 ~ t2 then t1 ~ t2. This is because every move is reversable and we can chain together two finite sequences of moves to create a new finite sequence of moves.

Consider the case now with k+1 disks and write t|k for the restriction of t from the domain {1,2,...,k+1} to {1,2,...,k}.

Suppose P(k) is true. Then for any state t of the k+1 pegs, t0|k ~ t|k by hypothesis. That is, if we start with all the disks on the leftmost peg, we can move the k smallest disks to any other configuration where the largest disk, disk #k+1 stays on the left peg. We can move, for example, the k smallest disks to any one peg.

Consider now an arbitrary state T of the k+1 disks where disk #k+1 is on one of the other pegs, Center or Right. Without loss of generality, assume it is Center. Then move the first k disks to the right peg. Now move disk #k+1 to the center. And now move all of the first k disks to their state T|k, something we can again do by hypothesis P(k).

Hence given P(k), we can move k+1 disks to an arbitrary configuration; i.e., P(k) => P(k+1).

Therefore by the Principle of Mathematical Induction, we can move n-disks to any state in the state space with a finite set of legal moves.