POW #2: Towers of Hanoi

There is a puzzle (often called ``The Towers of Hanoi'') consisting of three spindles, with a stack of nine rings of decreasing diameter stacked on the first spindle. The goal of the puzzle is to move all of the rings to the third spindle, while obeying the following rule: A ring at the top of a stack may be moved from one spindle to another spindle, provided that it is not placed on top of a smaller ring. Find the least number of moves that is required to move all nine of the rings from the first to the third spindle, and explain your answer.


Return to Laura Taalman, Burruss 127, by 10/22/03.