Four Towers of Hanoi on Circle (20 points) Suppose that the Tower of Hanoi’s pro

Question

Four Towers of Hanoi on Circle (20 points)
Suppose that the Tower of Hanoi’s problem has four poles A, B, C, D placed clockwise in a circle, and
disks can be transfered (one by one) from a pole to only the next pole in the clockwise direction. Also,
as in the original problem, at no time may a larger disk be palced on top of a smaller disk. Let t n be
the minimum number of moves needed to transfer the entire tower of n disks from A to B.
(a) Show that t n 5t n1 + 1, for n 2.
(b) Give an example of n 3, where t n is not equal to 5t n1 +1. Give the corresponding values of t n
and t n1 .

Explanation / Answer

here is a high-level outline of how to move a tower from the starting pole, to the goal pole, using an intermediate pole:

for t1,t2,t3

t1 = 1,

t2 = 1 + 1 + 1 = 3,

t3 = t1 + (1+1+1) + t1 = 5

for t4

t4 = s2 + (1+1+1) + t2 = 9

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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