# Thread: Tower of Hanoi Problem and skipping a move

1. ## Tower of Hanoi Problem and skipping a move

The Tower of Hanoi problem:

According to legend, a certain Hindu temple contains three thin diamond poles($\displaystyle A$, $\displaystyle B$, $\displaystyle C$ and $\displaystyle A$ is closer to $\displaystyle B$ and $\displaystyle B$ is closer to $\displaystyle C$ but $\displaystyle C$ is not closer to $\displaystyle A$) on one of which, at the time of creation, God placed $\displaystyle 64$ golden disks that decrease in size as they rise from the base.

The priests of the temple work unceasingly to transfer all the disks one by one from the first pole to one of the others, but they must never place a large disk on top of a smaller one and they are allowed to move disks from one tower to only adjacent pole. Let

$\displaystyle a_n = \left[ \begin{array}{c} \text{the minimum number of moves} \\ \text{needed to transfer a tower of n} \\ \text{ disks from pole A to pole C} \end{array} \right ]$

$\displaystyle b_n = \left[ \begin{array}{c} \text{the minimum number of moves} \\ \text{needed to transfer a tower of n} \\ \text{ disks from pole A to pole B} \end{array} \right ]$

Find a recurrence relation $\displaystyle a_n$ and $\displaystyle b_n$.

Solve for the problem to find $\displaystyle a_n$ (The book did this):

\displaystyle \begin{align*}\nonumber a_n =& a_{n-1} \text{ (moves to move the top n - 1 disks from pole A to pole C) } +\\ &\nonumber 1 \text{ (move to move the bottom disk from pole A to pole B) } + \\ & \nonumber a_{n-1} \text{ (moves to move the top disks from pole C to pole A) } + \\ & \nonumber 1 \text{ (move to move the bottom disk from pole B to pole C) } + \\ & \nonumber a_{n-1} \text{ (moves to move the top disks from pole A to pole C) } \\ \nonumber =& 3a_{n-1} + 2 \end{align*}

Solve for the problem to find $\displaystyle b_n$(I did this):

\displaystyle \begin{align*}\nonumber b_n =& b_{n-1} \text{ (moves to move the top n - 1 disks from pole A to pole C) } +\\ & \nonumber 1 \text{ (move to move the bottom disk from pole A to pole B } + \\ & \nonumber b_{n-1} \text{ (moves to move the top disks from pole C to pole B) } \\ \nonumber =& 2b_{n-1} + 1 \end{align}

Why my solution of $\displaystyle b_n$ is wrong? For finding $\displaystyle b_n$ I did the same thing as done in finding $\displaystyle a_n$ which is skipping the move from $\displaystyle A$ to $\displaystyle B$ when moving from $\displaystyle A$ to $\displaystyle C$. I calculated this move as $\displaystyle 1$ like the book did it.

So why am I wrong?

Also my question is why in finding $\displaystyle a_n$ to move the disks from $\displaystyle A$ to $\displaystyle C$ they skipped to calculate the move to move the disks first from $\displaystyle A$ to $\displaystyle B$?

2. ## Re: Tower of Hanoi Problem and skipping a move

Unless the rules contains some restriction that takes into account how close the poles are, $\displaystyle a_n$ should be equal to $\displaystyle b_n$. The recurrence equation is $\displaystyle a_n=2a_{n-1}+1$, and similarly for $\displaystyle b_n$.

3. ## Re: Tower of Hanoi Problem and skipping a move

Originally Posted by emakarov
Unless the rules contains some restriction that takes into account how close the poles are, $\displaystyle a_n$ should be equal to $\displaystyle b_n$. The recurrence equation is $\displaystyle a_n=2a_{n-1}+1$, and similarly for $\displaystyle b_n$.
I am bit confused. The poles are erected like Figure 1.

The rules for moving the disks are:
You can move disks from pole $\displaystyle A$ to pole $\displaystyle C$ via Pole $\displaystyle B$ you can't move disks directly to Pole $\displaystyle C$ from Pole $\displaystyle A$.
Same rule goes for pole $\displaystyle C$. You can't move disk directly from pole $\displaystyle C$ to Pole $\displaystyle A$. You've to go via Pole $\displaystyle B$.
You can move disks directly from Pole $\displaystyle A$ to pole $\displaystyle B$. Also you can move disks directly from Pole $\displaystyle C$ to pole $\displaystyle B$
You can move disks from Pole $\displaystyle B$ to Pole $\displaystyle A$ or to Pole$\displaystyle C$ directly . And you can't move larger disks on smaller disks.

You said that:

$\displaystyle a_n=2a_{n-1}+1$

Now $\displaystyle a_1 = 2$ because if you have $\displaystyle 1$ disk in pole $\displaystyle A$ it will take $\displaystyle 2$ moves to move $\displaystyle 1$ disk from pole $\displaystyle A$ to pole $\displaystyle C$ via pole $\displaystyle B$. you can't move a disk from pole $\displaystyle A$ to pole $\displaystyle C$ directly according to the rule stated above.

$\displaystyle a_2 = 8$ if you look at the Figure 1 you need minimum $\displaystyle 8$ moves to move $\displaystyle 2$ disks from pole $\displaystyle A$ to pole $\displaystyle C$ but you said $\displaystyle a_n=2a_{n-1}+1$

If we plug in the value of $\displaystyle n = 2$ we get:
$\displaystyle a_2 = 2a_{2-1} + 1 = 2a_{1} + 1 = 2*2 + 1 = 5 \neq 8 \text{(we got previously)}$

So shouldn't $\displaystyle a_n = \left[ \begin{array}{c} \text{the minimum number of moves} \\ \text{needed to transfer a tower of n} \\ \text{ disks from pole A to pole C} \end{array} \right ] = 3a_{k-1} + 2$?

The same goes for $\displaystyle b_n$

You said that $\displaystyle b_n = \left[ \begin{array}{c} \text{the minimum number of moves} \\ \text{needed to transfer a tower of n} \\ \text{ disks from pole A to pole B} \end{array} \right ] = 2b_{n-1} + 1$

Base condition is $\displaystyle b_1 = 1$ because to move a disk from pole $\displaystyle A$ to pole $\displaystyle B$ you need minimum $\displaystyle 1$ move according to the rules above.

Then if you look at Figure 1 it takes $\displaystyle 4$ minimum moves to move $\displaystyle 2$ disks from pole $\displaystyle A$ to pole $\displaystyle B$. So $\displaystyle b_2 = 4$

If we replace $\displaystyle n$ with $\displaystyle 2$ according to your equation:

$\displaystyle b_2 = 2b_{2-1} +1 = 2b_1 + 1 = 2* 1 + 1 = 3 \neq 4$

You can't take $\displaystyle 3$ move to move $\displaystyle 2$ disks from pole $\displaystyle A$ to pole $\displaystyle B$. It's impossible according to the rules stated above.

Can you kindly shed light what you said? Sorry I didn't get it. Also is it possible to get an answer to my question I posted first in this thread?

4. ## Re: Tower of Hanoi Problem and skipping a move

Sorry, I missed the adjacency requirement. It's not in the standard Towers of Hanoi rules.

The equation for $\displaystyle b_n$ should be $\displaystyle b_n=a_{n-1}+b_{n-1}+1$ since the first part is moving disks from A to C, which takes $\displaystyle a_{n-1}$ moves.

5. ## Re: Tower of Hanoi Problem and skipping a move

Originally Posted by emakarov
Sorry, I missed the adjacency requirement. It's not in the standard Towers of Hanoi rules.

The equation for $\displaystyle b_n$ should be $\displaystyle b_n=a_{n-1}+b_{n-1}+1$ since the first part is moving disks from A to C, which takes $\displaystyle a_{n-1}$ moves.
I know the subject should be "Modified Tower of Hanoi Problem....." Sorry for misunderstanding.