Tower of Hanoi Problem and skipping a move

Printable View

September 18th 2011, 06:43 PM
x3bnm

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( $A$ , $B$ , $C$ and $A$ is closer to $B$ and $B$ is closer to $C$ but $C$ is not closer to $A$ ) on one of which, at the time of creation, God placed $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

$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 ]$

$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 $a_n$ and $b_n$ .

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

$\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 $b_n$ (I did this):

$\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 $b_n$ is wrong? For finding $b_n$ I did the same thing as done in finding $a_n$ which is skipping the move from $A$ to $B$ when moving from $A$ to $C$ . I calculated this move as $1$ like the book did it.

So why am I wrong?

Also my question is why in finding $a_n$ to move the disks from $A$ to $C$ they skipped to calculate the move to move the disks first from $A$ to $B$ ?
September 19th 2011, 04:29 AM
emakarov

Re: Tower of Hanoi Problem and skipping a move

Unless the rules contains some restriction that takes into account how close the poles are, $a_n$ should be equal to $b_n$ . The recurrence equation is $a_n=2a_{n-1}+1$ , and similarly for $b_n$ .
September 19th 2011, 07:54 AM
x3bnm

1 Attachment(s)

Re: Tower of Hanoi Problem and skipping a move

Quote:

Originally Posted by emakarov

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

I am bit confused. The poles are erected like Figure 1.

Attachment 22316

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

You said that:

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

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

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

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

So shouldn't $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 $b_n$

You said that $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 $b_1 = 1$ because to move a disk from pole $A$ to pole $B$ you need minimum $1$ move according to the rules above.

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

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

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

You can't take $3$ move to move $2$ disks from pole $A$ to pole $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?
September 19th 2011, 08:23 AM
emakarov

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 $b_n$ should be $b_n=a_{n-1}+b_{n-1}+1$ since the first part is moving disks from A to C, which takes $a_{n-1}$ moves.
September 19th 2011, 08:32 AM
x3bnm

Re: Tower of Hanoi Problem and skipping a move

Quote:

Originally Posted by emakarov

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

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

I know the subject should be "Modified Tower of Hanoi Problem....." Sorry for misunderstanding.

And thanks for the answer.