Activity
In the Tower of Hanoi puzzle, a set of discs sits on a peg, while there are 2 other empty pegs.
A move in the Tower of Hanoi puzzle involves taking a disc and moving it to another peg. There are two rules:
- Only move 1 disc at a time.
- Never put a larger disc on top of a smaller one.
You complete the puzzle by building the complete tower on a different peg from the starting peg.
1. What is the smallest number of moves in which you are able to complete the puzzle with 3 discs?
Compare your answer:
7 moves
2. What is the smallest number of moves in which you are able to complete the puzzle with 4 discs?
Compare your answer:
15 moves
3. Jada says she used the solution for 3 discs to help her solve the puzzle for 4 discs. Describe how this might happen.
Compare your answer:
Jada moved the tower of discs 1 – 3, then moved disc 4, and then moved the remaining discs 1 – 3 onto it.
4. How many moves do you think it will take to complete a puzzle with 5 discs? Explain.
Compare your answer:
31 moves. For example: Double the previous answer, and then add 1. The number of moves is 31 because .
5. How many moves do you think it will take to complete a puzzle with 7 discs?
Compare your answer:
127 moves
In this activity, you have started to find a sequence of terms.
Write these definitions in your math notebook.
- A sequence is a list of numbers, possibly going on forever, such as all the odd positive integers arranged in order: 1, 3, 5, 7, . . . .
- The term (of a sequence) is one of the numbers in a sequence.
Self Check
Additional Resources
Using a Table to Find the Pattern
Sometimes it is helpful to keep a table to find the pattern needed to answer a question.
For the Tower of Hanoi game, enter the number of discs used and the smallest number of moves to solve the puzzle in a table like the one below. Use the answers from the activity.
| Number of Discs | 3 | 4 | 5 | 6 | 7 | 8 |
| Number of Moves to Solve Puzzle | 7 | 15 | 31 | ? | 127 | ? |
The pattern was to double the previous answer and then add 1.
Using this pattern, complete the table for 6 discs.
Then use this rule to find how many moves are needed to complete the puzzle with 8 discs.
There were 127 moves for 7 discs.
So, double 127 and add 1: .
Try it
Try It: Using a Table to Find the Pattern
Now it’s your turn. For the same game, how many moves would it take to solve the puzzle with 9 discs?
Your answers may vary, but here are some examples:
The pattern is still the same. Double the number of moves before and add 1.
With 8 discs, 255 moves were needed.
Double 255, and then add 1: