MathDB

The Tower of Hanoi is a puzzle with

n

disks of different sizes and

3

vertical rods on it. All of the disks are initially placed on the leftmost rod, sorted by size such that the largest disk is on the bottom. On each turn, one may move the topmost disk of any nonempty rod onto any other rod, provided that it is smaller than the current topmost disk of that rod, if it exists. (For instance, if there were two disks on different rods, the smaller disk could move to either of the other two rods, but the larger disk could only move to the empty rod.) The puzzle is solved when all of the disks are moved to the rightmost rod. The specifications normally include an intelligent monk to move the disks, but instead there is a monkey making random moves (with each valid move having an equal probability of being selected). Given

64

disks, what is the expected number of moves the monkey will have to make to solve the puzzle?

Problem Statement