In the Tower of Hanoi puzzle, n-rings initially are stacked on pole 1, 
the smallest on top down to largest on bottom.  The object is to get them 
into the same configuration on pole 3.  Also available is another pole 
called pole 2.  A move consists of taking the top ring off the stack on 
one of the poles and placing it on top of the stack on another pole, subject 
to the rule that a larger ring never can be placed atop a smaller ring.  
Imposition of the rule increases the minimum number of moves to solve the 
puzzle from 2n to 2n - 1.

Listed in the bibliography of "Claude Elwood Shannon: Collected Papers," 
but not included in the book, is a memo about the Tower of Hanoi.  This 
fact alone makes any paper about the Tower of Hanoi indisputably a contribution 
to information theory!  Neil Sloane informs me that in the memo Shannon 
describes how to build a machine that can work the puzzle for n=6 using the 
minimum number of relays; at the time, the “relay” was the preferred unit of 
computational complexity. 

Legend has it that monks in Hanoi have been moving a tower of 64 gold rings 
from pole 1 toward pole 3 for centuries and that, when they finish, the world 
will come to an abrupt end.  The less glamorous truth is that the puzzle and 
the legend both were invented in 1883 by the French mathematician, Eduoard Lucas.  
With n=64, several tens of quintillions of moves are required, so the world will 
not end imminently, even if it takes only a nanosecond to move a ring.  
Nonetheless, I advocate that the minimum path length strategy be abandoned in 
favor of a uniform Markov chain approach in which each move is chosen equiprobably 
from all the moves currently available.  There are always 3 moves available except 
when all the rings are on one pole, in which cases there are only 2.

I wish to determine the mean life of the world for the uniform Markov strategy 
as a function of n, call it Ln.   L1 = 2, L2 = 64/3, and L3 = 1274/9.  The Markov 
chain’s state diagram is a triangular fractal which, thanks to Neil, I now know is 
called the “Sierpinski gasket”, introduced in 1915 for entirely different purposes 
by the Polish mathematician, Vaclaw Sierpinski.  I‘ve developed a recursion that 
generates Ln+1 largely from items determined during computation of Ln.  However, 
it is too complicated to have let me deduce how En behaves asymptotically for the 
uniform Markov strategy.  It certainly increases to at least O(3n), but I suspect 
that the actual increase is dramatically greater.