- #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.
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
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
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: