The Average Distance between Nodes in the Cyclic Tower of Hanoi Digraph
Paul K. Stockmeyer · 1996
The cyclic Tower of Hanoi puzzle is similar to the traditional tower puzzle, but with the added restriction that all disks move between pegs in a clockwise direction, from peg A to B, from B to C, or from C to A. Many aspects of this puzzle have been analyzed, including the average distance in the state digraph from a random state to a designated goal state in which all disks are on one peg. Using similar but somewhat cleaner methods, we extend this result by computing the mean and variance of the distance between a random pair of states. Our results are compared to analogous ones for the traditional Tower of Hanoi puzzle. 1 Introduction and Background The Tower of Hanoi The famous Tower of Hanoi puzzle, invented in 1883 by the French mathematician ' Edouard Lucas [8], consists of three pegs, usually designated A, B, and C, and a set of n pierced disks of differing diameters that can be stacked on the pegs. By convention the disks are numbered from 1 to n in increasing order of siz...