# 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 2^{n} - 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.

### Reference

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