- #1

mr_coffee

- 1,629

- 1

Hello everyone.

I'm trying to figure this out, The problem says:

Suppose that the Tower of Hanoi problem has four poles in a row instead of three. Disk an be transfeered one by one from one pole to any other pole, but at no time may a larger disk be placed on top of a smaller disk. Let [tex]S_n[/tex] be the minimum number of moves needed to transfer the entire tower of n disks from the left-most to the right most pole.

Okay so i drew it out and I figured out the process:

if i have 4 poles, A, B, C, and D but I found an image on the web that will describe it better:

Then this is the process:

http://img100.imageshack.us/img100/908/untitledwc0.jpg [Broken]

Move n-2 disk from pole A to pole B,

then move top disk to pole C

then move top disk to pole D

Then move disk from C to D

The book says for a and b:

[tex]s_{1}[/tex] = 1

[tex]s_{2} [/tex]= 1 + 1 + 1 = 3

[tex]s_3 = s_1[/tex] + (1 + 1 + 1) + [tex]s_1[/tex] = 5

[tex]s_4[/tex] = [tex]s_2[/tex] + (1 + 1 + 1) + [tex]s_2[/tex] = 9

and if I keep going with this pattern i'll get:

[tex]s_5 = s_3 + (1 + 1 + 1) + s_3 = 13[/tex]

...

...

...

So it looks like they are getting the following formula:

[tex]s_k = s_{k-2}[/tex] + (1 + 1 + 1) + [tex]s_{k-2}[/tex]

[tex]s_k = 2*s_{k-2}[/tex]+ 3

So what I don't understand is, it says SHOW [tex]s_k <= 2*s_{k-2}[/tex] but I just showed up there that [tex]s_k = 2*s_{k-2}[/tex]

So is that all I had to do? Is list out some more terms and generalize a formula?

Thanks!

I'm trying to figure this out, The problem says:

Suppose that the Tower of Hanoi problem has four poles in a row instead of three. Disk an be transfeered one by one from one pole to any other pole, but at no time may a larger disk be placed on top of a smaller disk. Let [tex]S_n[/tex] be the minimum number of moves needed to transfer the entire tower of n disks from the left-most to the right most pole.

**c. Show that [tex]s_k <= 2*s_{k-2} + 3 [/tex]for all integers k >= 3.**Okay so i drew it out and I figured out the process:

if i have 4 poles, A, B, C, and D but I found an image on the web that will describe it better:

Then this is the process:

http://img100.imageshack.us/img100/908/untitledwc0.jpg [Broken]

Move n-2 disk from pole A to pole B,

then move top disk to pole C

then move top disk to pole D

Then move disk from C to D

The book says for a and b:

[tex]s_{1}[/tex] = 1

[tex]s_{2} [/tex]= 1 + 1 + 1 = 3

[tex]s_3 = s_1[/tex] + (1 + 1 + 1) + [tex]s_1[/tex] = 5

[tex]s_4[/tex] = [tex]s_2[/tex] + (1 + 1 + 1) + [tex]s_2[/tex] = 9

and if I keep going with this pattern i'll get:

[tex]s_5 = s_3 + (1 + 1 + 1) + s_3 = 13[/tex]

...

...

...

So it looks like they are getting the following formula:

[tex]s_k = s_{k-2}[/tex] + (1 + 1 + 1) + [tex]s_{k-2}[/tex]

[tex]s_k = 2*s_{k-2}[/tex]+ 3

So what I don't understand is, it says SHOW [tex]s_k <= 2*s_{k-2}[/tex] but I just showed up there that [tex]s_k = 2*s_{k-2}[/tex]

So is that all I had to do? Is list out some more terms and generalize a formula?

Thanks!

Last edited by a moderator: