Tower of Hanoi -- Algebraic Challenge

If you were born 100 years ago, you might have played with a "new" puzzle that was first sold as a toy in 1883 created by French mathematician Edouard Lucas. It was called the Tower of Hanoi or Tower of Brahma. Lucas was inspired by a legend that tells of a Hindu temple where the conical or pyramid puzzle was used for the mental discipline of young priests. Legend says that the priests in the temple were given a stack of 64 gold disks, each one a little smaller than the one beneath it (see page 2 of the pdf which shows a birds eye view of 64 concentric gold disks). The priests’ assignment was to transfer the 64 disks from one of the three poles to another. A large disk could never be placed on top of a smaller one. When the priests finished their work, the myth said, the temple would crumble into dust and the world would vanish. 

Are we in danger of this happening? The answer can be found in “Where is the Math?” below.

The actual Hindu temple in the legend is called the Kashi Vishwanath Temple. It is in the city of Varanasi , Uttar Pradesh, India and claims to be the oldest living city in the world, with 3500 years of documented history. The students and I also discussed other living cities such as Athens, Jericho, and Jerusalem which seem to have recorded histories older than Varanasi.

WHERE IS THE MATH?: The number of separate transfers of single disks the priests must make to transfer the 64 disk tower is 18,446,744,073,709,551,615 moves!! If the priests worked day and night, making one move every second, it would take slightly more than 580 billion years to accomplish the job. This is 127 times the current age of the Sun. Even if this legend were true, we have nothing to worry about. In fact, at this rate of moves (one per second), if the priests started 3500 years ago, in the year 1486BC, they would have finished the puzzle only if it had 36 disks.

The wooden Tower of Hanoi on page 1 of the pdf. has 32 disks, half that in the Tower of Brahma legend. It is in the Science Museum of the National Autonomous University of Mexico. 4,294,967,295 is the minimum number of moves to solve this puzzle. If we made one move per second all day, every day, it would take us 136 years 70 days to complete the transfer.

The children were introduced to algebra by learning the sequence of moves for n number of disks. For instance, the minimum number of moves for 0, 1, 2, 3, 4, 5, and n disks is 0, 1, 3, 7, 15, 31, and 2^n-1. At least one or two children in each group were able to solve this sequence of numbers by looking at the difference in the number of solutions. Each of the successive differences were powers of two (1,2,4,8,16,32, 2^n). Other children saw the recursive rule that you multiply the number of moves by two and then add one. For example, for 3 disks, 7 moves are required. So if we multiply 7 by 2 and add 1 or 7 + 7 + 1 = 15.

With some of the older groups I had time to let them explore this equation on a graphing calculator (one per child) and they were able to see the exponential growth of the graph. They also looked at the table of solutions and I had them scroll down to 64 disks to see the crazy number of 18 quintillion solutions. Some of the children were curious enough to ask about why there were solutions for negative number of disks. I would expect this level of questioning from a 6-8th grader. I explained that you cannot have a negative number of disks so those solutions are nonsensical. I hope my explanation made sense.

I asked the children if they wanted to try to do 64 disks or use the pattern of numbers we found. They all chose the pattern of numbers.  This is exactly why algebra is so powerful. 

I gave the children materials to make their own Tower of Hanoi with up to 7 disks. I even included golf tees for the towers. Here is their quest for the week:

1. Cut out the three peg (A, B, C) board and the seven colored disks to create your own Tower of Hanoi (disks 6 and 7 are on page 7 of the pdf). Glue the three golf tees vertically to the Tower of Hanoi board on the dots above the letters A, B, and C. I precut holes in the middle of disks 1-5 since they were hard stock paper. They should push down each disk onto the golf tee to open the hole.

2. Solve this puzzle with 3 disks, 4 disks and 5 disks and record each move with the number of the disks and the letter of the peg on the worksheet provided. Also, record the total number of moves for each number of disks transferred. For example, one solution for 4 disks is 1B, 2C, 1C, 3B, 1A, 2B,1B. The older children can record the solutions for 6 and 7 disks, 63 and 127 solutions, respectively.

3. Try to find patterns as you increase the number of disks. Can you make predictions as to number of moves for increasing the number of disks to 6, 7, 8 ....? HOW HIGH CAN YOU GO?

I hope the children have this game to play with for years to come.