Friday, February 26, 2016

Towers of Hanoi: A Mathematical Puzzle

The Tower of Hanoi is a mathematical puzzle.  As you can see below, there are three rods and a number of disks of difference sizes.
Clicking this image leads to an Amazon affiliate link

The puzzle starts with the disks stacked on one rod in ascending order of size (with the smallest on the top, and the largest on the bottom). The objective is to move the entire stack to another rod.  The hard part is that you can only move one disk at a time, and you can never put a larger disk on top of a small disk.

If you have n disks (in the picture above, n = 10), what's the minimum number of moves this can be accomplished in?  It turns out that the answer is 2^n - 1.  So 3 disks would take 7 moves, but the 10 disk example above would take 1023 moves!  This is a good illustration of how quickly exponential functions grow.

The Tower of Hanoi makes for a great lecture, math circle activity, and toy to play with! Have your students make a table of examples, building up from n = 1, try to figure out a pattern, and prove it!

There's also a great legend behind the puzzle. According to Wikipedia:
The puzzle was invented by the French mathematician Édouard Lucas in 1883. There is a story about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the immutable rules of the Brahma, since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle will be completed, the world will end.  It is not clear whether Lucas invented this legend or was inspired by it.
 If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves, it would take them 264−1 seconds or roughly 585 billion years or 18,446,744,073,709,551,615 turns to finish, or about 127 times the current age of the sun.

No comments:

Post a Comment