Five Towers of Hanoi (30 points) Suppose that the Tower of Hanoi’s problem has f
ID: 3810172 • Letter: F
Question
Five Towers of Hanoi (30 points) Suppose that the Tower of Hanoi’s problem has five poles in a row. Disks can be transfered one by one from one pole to any other pole (there is no adjacency requirement), but at no time may a larger disk be palced on top of a smaller disk. Let tn be the minimum number of moves needed to transfer the entire tower of n disks from the left-most to the right-most pole. (a) Show that tn 2tn2 + 3, for n 3. (b) Give an example of n 3, where tn is not equal to 2tn2 + 3. Give the corresponding values of tn and tn2. (c) Show that tn 2tn3 + 5, for n 3.
Explanation / Answer
There are 5 poles according to the problem
a.Show that tn <= 2tn2 + 3, for n >= 3.
if n=3
the minimum moves = 5
2tn-2+3 = 2*5-2+3 = 11
hence tn <= 2tn-2+3
b.Give an example of n 3, where tn is not equal to 2tn2 + 3
if n=4
the minimum moves = 7
2tn2 + 3 = 2*7-2+3 = 15
hence tn is not equal to 2tn-2+3
value of tn = 15
value tn-2 = 13
c.Show that tn 2tn3 + 5, for n 3.
if n=3
the minimum moves = 5
2tn-3+5 = 2*5-3+5 = 12
hence tn <= 2tn-3+5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.