Daniel Berend

The Tower of Hanoi problem with h ≥ 4 pegs is long known to require a sub-exponential number of moves in order to transfer a pile of n disks from one peg to another. In this paper we discuss the Path;, variant, where the pegs are placed along a line, and disks can be moved from a peg to its nearest neighbor(s) only. Whereas in the simple variant there are h(h -1)/2 bi-directional interconnections among pegs, here there are only h -1 of them. Despite the significant reduction in the number of interconnections, the task of moving n disks between any two pegs is still shown to grow sub-exponentially as a function of the number of disks.