Towers of Hanoi

[Taken from this history of computer science.]

Greg and Genny Grinnellian have taken summer internships at Bell Labs.

In the musty basements of Bell Laboratories, there are a number of varying sized reels of tape stacked on top of each other in a bin. There are three bins in which reels of tape can be placed. Each reel of tape can only be stacked on top of larger reels.

After arriving at Bell, Greg and Genny have discovered that their first task is to move all of the reels of tape from the first bin to the third bin. The reels of tape are so fragile that they can only move one reel at a time, and must work together to move the reel. The reels can only be stored in bins (not on the floor or elsewhere). For some reason, all of the reels are labeled "Hanoi".

We begin with all the reels in the leftmost bin. For now, we'll assume that there are just three reels.

|  X  | |     | |     |
| XXX | |     | |     |
|XXXXX| |     | |     |
+-----+ +-----+ +-----+
 Left    Center  Right

Their goal is to get all of the reels into the right bin, as in

|     | |     | |  X  |
|     | |     | | XXX |
|     | |     | |XXXXX|
+-----+ +-----+ +-----+
 Left    Center  Right

Suggest a strategy that they should use to move the tapes. Recall that only one tape can move at a time, and it is illegal to put larger tapes on top of smaller tapes.

Would they use a different strategy if there were four tapes?

By the way, an interactive version of this problem is also available. (A Java-capable browser is required.)

[Front Door] [Problems] [Resolutions] [Essays] [Resources] [Miscellaneous]

Warning! This site is under development.

Source text last modified Tue May 5 20:08:05 1998.

This page generated on Thu May 7 14:25:09 1998 by SiteWeaver.

Contact our webmaster at