Tower of Hanoi Poles in a Circle: Suppose that instead of

Chapter 5, Problem 20E

(choose chapter or problem)

Problem 20E

Tower of Hanoi Poles in a Circle: Suppose that instead of being lined up in a row, the three poles for the original Tower of Hanoi are placed in a circle. The monks move the disks one by one from one pole to another, but they may only move disks one over in a clockwise direction and they may never move a larger disk on top of a smaller one. Let cn be the minimum number of moves needed to transfer a pile of n disks from one pole to the next adjacent pole in the clockwise direction.

a. Justify the inequality ck ≤ 4ck–1 + 1 for all integers k ≥ 2.

b. The expression 4ck-1 + 1 is not the minimum number of moves needed to transfer a pile of k disks from one pole to another. Explain, for example, why

c3 ≠ 4c2 + 1.