Consider a Double Tower of Hanoi. In this variation of the Tower of Hanoi there

Question

Consider a Double Tower of Hanoi. In this variation of the Tower of Hanoi there are three poles in a row and 2n disks, two of each of n different sizes, where n is any positive integer.

Assume one of the poles initially contains all of the disks placed on top of each other in pairs of decreasing size. Disks are transferred one by one from one pole to another, but at no time

may a larger disk be placed on top of a smaller disk. However, a disk may be placed on top of one of the same size. Let an be the minimum number of moves needed to transfer a tower

of 2n disks from one pole to another.

(a) Find a1, a2, and a3.

(b) Derive a recurrence relation for the sequence a1, a2, and a3    and check that the results in (a)

satisfy your recurrence relation.

(c) Show that the formula an = 2n+1 - 2 for the nth term in the sequence satisfies the recurrence relation you derived in (b).

Please explain your provided answer

Explanation / Answer

a) a1= 2

a2 = 6

a3 = 14

b) Assume we know the solution for an-1 (2n-2 disks),

Now for an (2n disks), we have to move 2n-2 disks to the auxillary tower, then the last 2 disks to the destination tower, which will take 2 moves. Now, move the 2n-2 disks from auxillary tower back to the destination tower over top of those last two disks. thus, total moves = 2an-1+2 = an

c) an=2n-1-2

Put n= 1,2 and 3 in an

You will notice that the respective values matches the respective answers in (b)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.