The Tower of Hanoi is a puzzle invented by a French mathematician named Édouard Lucas in 1883. The game actually has nothing to do with Hanoi or Vietname, and we can assume that Lucas chose the name in an attempt to give it an air of exotic mystique. (In 1883 what is now the independent nation of Vietnam was at the time part of a region that was being colonized by France.)
The game consists of a stack of disks, the "tower", with three possible locations to put the disks. The goal is to move the entire tower from one location to another, with two rules:
There is also a legend related to this game. The story goes that there is a temple in India. Inside this temple are three ancient, worn wooden posts, and 64 golden disks on the posts...just like the Tower of Hanoi game. The Brahmin priests in this temple are following the an ancient prophecy, which commands them to move the disks according to the rules above. According to the legend, when the last disk is moved into place, the world will end. (It is unknown whether Lucas was inspired by this legend or if he invented it.)
Can you figure out how to solve the puzzle? If you can move 1 disk per second, how long would it take to finish a puzzle with 4 disks? How about with 64 disks?