Towers of Hanoi
From Sciencetheatre
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.
Contents |
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
- Set out the Towers of Hanoi. Each one gets four washers, stacked from biggest to smallest on one side.
- 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:
- They can only move one washer at a time, with each move counting as one step.
- They cannot stack a larger washer on top of a smaller washer.
- When they find an answer, they have to show it to you.
- 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 = 2^{n} - 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.
This same counting method works just as well on your fingers! Using either hand, label your thumb as "1", your forefinger as "2", your middle finger as "4", your ring finger as "8" and your pinkie as "16". Start with your hand closed, and count by putting your fingers up. For example, if you count "11", then you would have your thumb "1", forefinger "2" and ring finger "8" up, which add to 11. This method allows you to count up to 31 on a single hand, and with both hands you could count all the way to 1,023!
Additional Information
- Once students figure out the equation, have them calculate how many steps you would need for 10, 20, or 100 rings!
- This demonstration pairs well with the Binary Plinko.