The Tower of Hanoi is a popular puzzle invented by E. Lucas in 1883. The idea is that there are n disks arranged from largest to smallest on one rod together with two empty rods. What is the smallest number of moves that must be made in order to transfer the disks completely from one rod to an adjacent one if:
1) Only one disk may be moved at a time.
2) A large disk may not rest on top of a smaller one.
Hint: Use induction. First, try n = 2, then n = 3, etc and determine the pattern.
Challenge: What is the most efficient algorithm for moving these disks?