# 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.
All times are GMT -8. The time now is 11:42 PM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 12, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9372614026069641, "perplexity_flag": "middle"}