Towers of Hanoi Problem

Printable View

November 29th 2010, 06:28 PM
SMAlvarez

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:

Quote:

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.
November 30th 2010, 02:22 AM
emakarov

Quote:

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$ .
November 30th 2010, 07:35 AM
SMAlvarez

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

Also, is there a equation for bk?
November 30th 2010, 07:59 AM
SMAlvarez

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!!
November 30th 2010, 08:42 AM
emakarov

Quote:

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.

Quote:

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.

Quote:

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.

Quote:

The book says b4=40

I agree.