Key concepts
Mathematics
Patterns
Algorithms
Puzzles

Introduction
Are you tired of math work sheets and homework? Did you know that there are more creative ways to exercise your mathematical muscle? A lot of games, puzzles and riddles revolve around mathematical concepts. Think about simple games such as tic-tac-toe, more strategic games such as chess or math puzzles such as sudoku. People have been playing these games and puzzles for centuries! They are fun, entertaining and sometimes useful. See how you enjoy this one.

Background
Throughout history mathematics has fulfilled many practical needs such as measuring plots of land, studying astronomy and calculating taxes. But math can also be used for entertainment—mathematical games, riddles, challenges and puzzles are also interwoven throughout history!

The tower of Hanoi (also called the tower of Brahma or the Lucas tower) was invented by a French mathematician Édouard Lucas in the 19th century. It is associated with a legend of a Hindu temple where the puzzle was supposedly used to increase the mental discipline of young priests. In the legend the young priests were given 64 gold disks stacked neatly on one of three posts. Each disk rested on a slightly larger disk. The priests' goal was to re-create the stack on a different post by moving disks, one at a time, to another post with the rule that a larger disk could never be placed on top of a smaller disk. Using mathematics, you can calculate that even when the priests found the most efficient way to solve the problem, and moved the disks at a rate of one per second, it would take almost 585 billion years to finish the job. That is more than 40 times the age of the universe!

You might wonder how mathematics is involved in playing this game. As you play the game with more and more disks, you will notice you start to look for patterns. If you try to explain how you solve the puzzle, you might realize you use one of the following mathematical concepts:
—Iterative solutions, where the same sequence of instructions is repeated over and over
—Recursive solutions, where you use information from one step to find the next step
—Patterns and translating these in mathematical formulas.
These terms might seem hard to understand. Don’t worry! Play the game, and you might realize that you develop these “solutions” on your own.

Materials

• Five different-size disks such as buttons, bottle caps, container lids, etcetera (The biggest disk needs to have a diameter no larger than five inches.)
• Cardboard, about five by 15 inches
• Marker
• Ruler

Preparation

• Draw two straight lines to divide the cardboard into three equal-size squares (about five by five inches each).

Procedure

• Start the game with your two smallest disks. Stack them on the leftmost square of your cardboard, with the smaller disk on top of the larger disk.
• The starting position of the game is a tower on the leftmost square of the board (like the two-disk tower you have now). The goal of the game is to move the tower to the rightmost square of the board while following these rules:

—You can only move one disk at a time.

—You can only move the topmost disk from any square.

—Disks can be placed on an empty square on the board or on a larger disk, but disks cannot be placed next to each other on top of a larger disk.

• Looking at the rules, can you see it is not allowed to place a disk off the board? Where does it state you cannot start two towers on one square?
• Try the game with your two-disk tower. Can you move the tower to the rightmost square, following the rules above? How many moves did you need? If you get confused or cannot finish the game, ask a friend to help you.
• Replay the game with the two-disk tower. Do you think you can find the “best” solution, with the smallest possible number of moves?
• Once you master the two-disk tower, try with three disks. Stack three disks (from largest to smallest) on the leftmost square and start over. How many moves did you need this time?
• Try the game again with three disks. Can you finish the game with fewer moves? Do you think you can finish the game with the smallest possible number of moves?
• Now try with four disks. Can you find a way to do it in as few moves as possible? Does anything you learned while solving the three-disk tower help you solve the four-disk one?
• Play the game a few more times and observe closely. Do you have a strategy? Could you explain to a friend how you finish the game?
• Challenge yourself and try the five-disk tower. If you had a strategy, can you extend it to the five-disk tower?
• If you did not have a strategy yet, do not give up! See if you can find a pattern now. Can you find the smallest number of moves needed to finish the five-disk game? How many more moves would you need compared with the four-disk one? How many more moves are needed to move the four-disk tower compared with the three-disk one?
• Extra: Did you find a single strategy that works to solve the puzzle for two, three, four or five disks? Can you write down the steps for this strategy so you always remember how you solved the puzzle? This list of steps is called an “algorithm.”
• Extra: Can you try your algorithm on a different number of disks? Does it still work, or can you adjust it to make it work?
• Extra: If you found the minimal number of moves required to solve the puzzle for two, three, four or five disks, can you see a pattern in the minimal number of moves required? Could you use the pattern to predict the minimal number of moves required for a game with six disks? Maybe you can even find an equation to calculate the minimum number of moves required to play a game with a certain number of disks. (Note: the equation involves exponents.)
• Extra: There are many variations of the Tower of Hanoi game. For example, you can arrange the squares in a circle and only allow disks to move clockwise. Look up some other variations of the game. How do the new rules change the solutions you can find? Can you write algorithms to solve the modified versions?

Observations and results
Were you able to move the two-disk stack in three moves? Three is the minimal number of moves needed to move this tower. Maybe you also found in the games three-disks can be finished in seven moves, four-disks in 15 and five-disks in 31.

To play the two-disk game with only three moves, place the small disk on the middle square, the bigger one on the rightmost square and finish by placing the smaller disk on the bigger one. A way to play the three-disk game is to move the topmost two-disk stack to the middle square. This is a slight variation of the two-disk game and can be done in three moves. Then move the biggest disk from the leftmost to the rightmost square (one move). Next move the two-disk stack that is now in middle square on top of the biggest disk. Again a slight variation of the two-disk game, which can be done with three moves. This yields 3 + 1 + 3, or seven moves. A similar approach helps play the four-disk game. First move the topmost three-disk stack to the middle square using seven moves. Then move the biggest disk from the leftmost to the rightmost square (one move). Now move the three-disk stack that is in middle square on top of the biggest disk (seven moves). This yields exactly 7 + 1 + 7, or 15 moves. Mathematicians call this is a recursive procedure. To solve the puzzle with more disks, you start out with the solution for a smaller number of disks.

There are other ways to play the game. There is a pattern used to start the game when played with a minimal number of moves: The smallest disk goes to the rightmost square when playing with an even number of disks and to the middle square when playing with an odd number of disks. Maybe you also noticed you alternate between moving the smallest and the next-smallest movable disk while playing the game. If you pay close attention, you might note that you repeat the same set of instructions over and over until the tower appears on the other side of your board. Mathematicians call this is an iterative solution.

More to explore
Tower of Hanoi, from The Math Forum
Making Room for Math, from Science Buddies
Statistical Science: Melt-in-Your-Mouth Math, from Scientific American
Science Activities for All Ages!, from Science Buddies

This activity brought to you in partnership with Science Buddies 