Thread: Towers of Hanoi Problem2

Hey,

I need the reccurence relation equation for question C.

Here is what I think it is:

sk = sk-1 +3 + sk-1

because s1=1, s2=1+1+1=3

s3=s1 +(1+1+1) + s1 =5

s4=s2 + (1+1+1)+s2=9

Am I correct with the reccurence relation equation? BTW do I need this for question c?

The problem is as follows:

1. Four-pole Tower of Hanoi: Suppose that the Tower of Hanoi problem has four poles in a row instead of three. Disks can be transferred one by one from one pole to any other pole, but at no time may a larger disk be placed on a smaller disk. Let sk be the number of moves to transfer an entire tower of k disks from the left-most pole (A) to the right-most pole (D).
a. Find s1, s2, and s3.
b. Find s4.
c. Show that sk <= 2sk-2 + 3 for all integers k>=3.

I believe the definition should say that is the least number of moves to transfer k disks. You created some algorithm for moving disks; this shows that . This solves problem c. If you want to show that , then you also need to show that , i.e., that there does not exist a more efficient algorithm.

In fact, Wikipedia says, "Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem."