ABSTRACT
The traditional Tower of Hanoi puzzle consists of three pegs with 64 different sized rings stacked on one of them. The rings are arranged in decreasing order with the larger one on the bottom and the smallest one on the top of the stack. The problem is to move the rings one at a time from one peg to another, never putting a larger one on a smaller one, and eventually transferring all 64 rings from one peg to another peg. If the number of pegs is infinite, one can put N – 1 rings each on a single peg, then move the bottom ring and replace the N – 1 rings on it. This requires 2N – 1 moves. Any time the number of pegs is greater than the number of rings, the situation is equivalent to having an infinite number of pegs and hence the answer is 2N – 1.
