next up previous
Next: Polygonal Ears Up: Problems Previous: Pairing Off People

Towers of Hanoi

The Towers of Hanoi puzzle consists of three posts and n disks of different sizes that are initially stacked on one of the posts, from largest to smallest with the largest disk on the bottom. The goal is to move this stack of disks to a different post by a sequence of moves. Each move consists of moving the disk from top of the pile on any post to the top of the pile on any other post, as long as a larger disk is never placed directly on a smaller one. Try to solve this puzzle with n=7. Can you find a general procedure for n disks? How many moves are required?

Carl Lee
Wed Apr 21 08:26:07 EDT 1999