# Math Help - Towers of Hanoi Problem

1. ## Towers of Hanoi Problem

I need help getting started I believe bk=ak-1, but I'm not sure.

Can someone show me how to get B1 and I will attempt the rest? Thanks.

The problem is:

1. Tower of Hanoi with Adjacency Requirement. Suppose that in addition to the requirement that they neer move a larger disk on top of a smaller one, the priests who move the disks of the Tower Hanoi are also required to move disks one by one from one pole to an adjacent pole. Assume poles A and C are at the two ends of the row and pole B is in the middle. Let
an = the minimum number of moves needed to transfer a tower of n disks from pole A to pole C.
The recurrence relation for ak is then ak = 3ak-1+2.
Now let
bk=the minimum number of moves needed to transfer a tower of n disks from pole A to pole B.
a. Find b1, b2, and b3.
b. Show that bk=ak-1+1+bk-1 for all integers k>=2.
c. Show that bk <= 3bk-1+1 for all integers k>=2.

2. Can someone show me how to get B1 and I will attempt the rest?
Are you really wondering how many moves it takes to move one disk from A to B?

It is easy to see that $b_2=4$. In my opinion, it is easier to see why the general formula for $b_k$ holds than to calculate $b_3$ from scratch. This, of course, will allow you to figure $b_3$ provided you know $a_1$.

3. Yes how many steps does it take to move from a to b?

Also, is there a equation for bk?

4. Also how did you get b2 = 4?

The book says b4=40

also when I say equation I mean like ak = 3ak-1+2.

THANKS!!

5. Also, is there a equation for bk?
There is a recurrence equation in your first post, though it expresses $b_k$ through both $b_{k-1}$ and $a_{k-1}$. Most likely, it is possible to express $b_k$ through $b_{k-1}$ only, but the problem does not ask for this.

Yes how many steps does it take to move from a to b?
Move what? Moving one disk from A to B is something you'll have to figure out for yourself. Also, be careful about capital/lowercase letters: A and B denote poles while $a_k$ and $b_k$ are numbers.

Also how did you get b2 = 4?
Move the smaller disk to C (2 moves because of the adjacency requirement), move the larger disk to B, move the smaller disk to B.

The book says b4=40
I agree.