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. Initially one of the poles contains all 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 tn be the minimum number of moves needed to transfer a tower of 2n disks from one pole to another.

a. Find q and t2.

b. Find t3.

c. Find a recurrence relation for t1, t2, t3, ....

Question

contestada

Respuesta :

batolisis batolisis · Answer 1 · 2021-07-31T21:01:06+02:00

Answer:

a) t1 = 2 , t2 = 6

b) t3 = 14

c) recurrence relation ( Tn ) = 2Tn-1 + 2

Step-by-step explanation:

Tn = minimum number of moves needed

2n disks is moved from one pole to another

a) determine the value of t1 and t2

let n = 1

2n moves = 2 * 1 = 2

∴ t1 = 2

let n = 2

2n moves = 2*2 = 4

∴ t2 = 4 + t1 = 4 + 2 = 6

b) determine value of t3

let n = 3

2n moves = 2 * 3 = 6

∴ t3 = t1 + t2 + 6

= 2 + 6 + 6 = 14

c) Determine th recurrence relation

let n ≥ 2 i.e. n - 1 ≥ 1

number of disk required to be moved = 2n

number disks as follows : 1 to 2n

the recurrence relation = sum of number of moves in each step

Tn = Tn-1 + 2 + Tn -1

hence recurrence relation ( Tn ) = 2Tn-1 + 2 when all integers n ≥ 2