Tower of Hanoi

Tower of Hanoi

The Tower of Hanoi is a game invented by Edouard Lucas and sold as a toy in 1883. Early versions of it carried the name "Prof. Claus" of the College of "Li-Sou-Stain," but these were quickly discovered to be anagrams for "Prof. Lucas" of the College of "Saint Louis." The game, in its usual form, consists of three pegs on one of which are eight disks, stacked from largest to smallest. The problem is to transfer the tower to either of the vacant pegs in the fewest possible moves, by moving one disk at a time and never placing any disk on top of a smaller one. The minimum number of moves turns out to be 2n - 1, where n is the number of disks; this equals 255 in the case of an eight disks. The original toy came with a description saying that it was a small version of the great Tower of Brahma.



1. Poole, D. G. "The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi)." Math. Mag., 67: 323-344 (1994).