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 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
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