[Math] Is it possible to play the Tower of Hanoi with fewer than $2^n-1$ moves

discrete mathematicsinduction

The Tower of Hanoi game consists of three identical upright pegs and n rings all of different diameters that can be stacked over any of the pegs. Initially, all of the rings are stacked around one of the pegs in order of decreasing diameter with the largest ring on the bottom. The object of the game is to transfer all the rings, one at a time, until they are stacked in the same order around another peg, but at no time may any ring be placed above a ring of smaller diameter.

Prove that, for any number of rings, the transfer can be made in exactly $2^n-1$ moves.

We need to use induction…

Basis Step

IF we let $n=1$, then the left hand side must be 1 and the right hand side must be one as well.

$1 = 2^1-1$

$1 = 1$

Induction Step.

If $P(k)$ is true, then we can move $k$ disks in $2^k-1$ moves.

If $P(k+1)$ is true, then we can move $k+1$ disks $2^{k+1}-1$

Let $2^k – 1 $ be the number of moves for $k$ disks. Then,

$2(2^k-1)+1$

Using our induction hypothesis, we have

$2(2^{k+1}-1)$.

For any $ k \geq 1$, $P(k)$ and $P(k+1)$ is true.

Edit: This isn't right at all… it's just fluff…I need to start over.

Can the Tower of Hanoi be played in less than $2^n-1$ steps?

This is where I'm stuck… My guess is that unless you break the rules of the game, then you can't play in fewer steps. Do I use induction to prove that it's impossible or possible?

Best Answer

Actrually it is impossible to do this, it really need $2^{n}-1$ moves.

We can prove it in the following way:

Let $a_{n}$ be the number of moves to finish a Hanoi with $n$ disks. Now we prove that $a_{n}=2^{n}-1$.

  1. For $n=1$, we just need one move, so $a_{1}=1=2^{1}-1$, equation holds when $n=1$.

  2. We suppose equation holds when $n=k$, that is to say $a_{k}=2^{k}-1$.

    For $n=k+1$,

    a) We first need to move the top $k$ disks from pile A to B by using pile C, it costs $2^{k}-1$ moves.

    b) Then we need to move the last disk from pile A to C, which just costs one move.

    c) At last, we need to move all the $k$ disks from pile B to C by using pile A, it costs another $2^{k}-1$ moves.

    Now, we have already finish the game when $n=k+1$.

    Let calculate $a_{k+1}$, it will be like this by adding all the moves above

    $$a_{k+1}=a_{k}+1+a_{k}=2a_{k}+1=2\left(2^{k}-1\right)+1=2^{k+1}-1.$$

    Equation holds when $n=k+1$.

From 1. and 2. we can arrive the conclusion that $a_{n}=2^{n}-1$.

So it is impossible to finish a Hanoi game by using less than $2^{n}-1$ moves.

Related Question