Tower of Hanoi, 4 pegs i'm not sure what they are asking

[mr_coffee]

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 S_n 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 s_k <= 2*s_{k-2} + 3for 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:

s_{1} = 1
s_{2}= 1 + 1 + 1 = 3
s_3 = s_1 + (1 + 1 + 1) + s_1 = 5
s_4 = s_2 + (1 + 1 + 1) + s_2 = 9


and if I keep going with this pattern i'll get:
s_5 = s_3 + (1 + 1 + 1) + s_3 = 13
...
...
...
So it looks like they are getting the following formula:
s_k = s_{k-2} + (1 + 1 + 1) + s_{k-2}
s_k = 2*s_{k-2}+ 3

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

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

Thanks!

 

[matt grime]

I'm struggling to work out your question owing to your notation.. Please go through it again and make sure when you don't write s_k-2 when you really mean (s_k) -2 or s_{k-2}. And what does == mean? (Third line from bottom.)

 

[mr_coffee]

sorry matt i fixed it, i hope latex didn't modify my orginal.
== i mean is equal too, i fixed it above as well.

 

[matt grime]

The issue is simply this:

you've shown that it is possible to move across in 2s_{k-2}+3 moves. You have not justified that the plan you set out above is actually the optimal strategy - it is conceiveable that there is a better way of doing it (there isn't as it happens). Thus you have shown that there is an algorithm that takes 2s_{k-2} + 3 moves, hence the best one takes s_k<= 2s_{k-2} +3 moves.

 

[ashoka]

Your solution can actually be improved. rather than building a tower of 8 in the second tower, you could build a tower of size 5 there. then put next 4 biggest rings in tower 3 and finally move the biggest ring to the target tower. This way it will take you only 49 steps. Thus the formula given in the question is correct. There really is shorter solutions. What you have found is the longest of possible solutions hence =<

some more information. when you make the tower with height 5, you use all 4 towers to help build it. but once you make it, you keep it as it is and build your next tower only using the remaining 3 towers (like in the case of standard puzzle).

http://iq-games.blogspot.com/2011/02/bringing-down-towers-of-hanoi-part1.html

 

[ashoka]

I have included the solution for 4 tower case. Please have a look http://iq-games.blogspot.com/2011/04/towers-of-hanoi-part-8.html" .

Havn't seen this algorithm before anywhere, if any of you have seen it, please let me know.

Also in part 4,5 and 6 you will see the solution (in java) for the general case of 3 tower problem. (having all rings in the first tower at start is just a subset of this, general case is much more interesting and bit more challenging in recursion)

Cheers