# Towers of Hanoi

 Math, Engineering: Exponential Growth, Binary Systems Grade Range: Elementary School, Middle School Format: Hands-on

This demonstration is made to make students think, so let them attempt it for a minute before explaining anything.

## Materials

• Peg Blocks
• Washers
• Pencils and Paper
• Optional: Explanation Poster

## Safety Precautions

Please read the General Safety section of the Demonstration Safety page before performing this demonstration.

## Demonstration

1. Set out the Towers of Hanoi. Each one gets four washers, stacked from biggest to smallest on one side.
2. When students come up to the demonstration, explain to them that they are to find the smallest number of steps needed to move the stack of washers from one peg to another. They must follow these rules:
1. They can only move one washer at a time, with each move counting as one step.
2. They cannot stack a larger washer on top of a smaller washer.
3. When they find an answer, they have to show it to you.
3. Allow students to play with the Towers of Hanoi. Encourage students to try it with one, two or three rings before trying it with four, and to write down the number of steps each one takes. Can they solve the pattern?

## Why This Works

The Towers of Hanoi are a classic puzzle developed in 1883 by Ă‰douard Lucas, a French Mathematician. The goal is to move a stack of rings from one peg to another in the fewest steps possible. However, you cannot move more than one ring at a time, and you cannot stack a larger ring on top of a smaller ring. This is easy to do with only two rings, and it isn't too hard with three, but it starts to get complicated with four rings. This is because it is an exercise in exponential growth, or rapid growth within a system.

 Number of Rings Number of Steps 1 1 2 3 3 7 4 15 Rings = n Steps = N N = 2n - 1

If we look at this chart, we see how the number of steps needed increases quickly as we add more rings. By looking at the number of steps versus the number of rings, we can see that there is a pattern to it: The number of steps increase each time by a multiple of two. The number of steps, however, are also one less than a multiple of two. This gives us enough information to solve for the equation: The number of steps (N) is equal to 2 to the power of the number of rings (n) minus 1.

This number pattern with the rings can also be used to show how a binary counter works. We can think of each ring in the stack being equal to a value twice as much as the one above it, with the smallest ring equal to one, the next ring equal to two, the third ring equal to four, and the fourth ring equal to 8. If we assign these values to the rings, then we can solve how many steps it will take for a stack by adding up the ring values in the stack. Not only that, but we can then use the rings to count, and be able to count from 0 to 15 using only four inputs. If we were to add a fifth input, then the fifth ring would be equal to 16, and we could count from 0 to 31.