What it shows
Discs of different sizes must be moved from one peg to another, one at a time, never putting a larger disc on a smaller one. The least number of moves is 1, 3, 7, 15, 31 and 63 for 1 to 6 discs, which is 2 to the power n minus 1, so 64 discs would take more than 18 quintillion moves.
The science
To move n discs you must first move the n minus 1 smaller discs out of the way, then move the largest disc once, then move the n minus 1 discs back on top. So moves(n) = 2 times moves(n minus 1) + 1. Starting from 1 move for one disc, this gives 3, 7, 15, 31, 63, which is 2 to the power n minus 1. The puzzle is a classic example of recursion, where a problem is solved by solving a smaller copy of itself.
Materials
Cost: free. Many items come from home or from waste; spare parts such as LEDs, motors and wire are in the store.
- Six lids or caps of clearly different sizes, from a bottle cap to a jar lid
- Three pegs: pencils stuck upright in a plank or clay base
- A stopwatch
- A record sheet
Safety
For this project: An adult must fix the pegs; blunt the pencil tops.
Never use mains electricity: power models with cells, batteries or a low-voltage adapter. Sharp and hot tools, flames and lab chemicals need an adult or your teacher beside you. Keep magnets, button cells and small parts away from young children, and wash your hands after making.
All the safety rulesStep by step
8 steps. Do them in order, and test each part before you go on to the next. Write what you notice in a notebook as you go.
Drill or press three pegs into the base, far enough apart that the largest lid fits between them, and make a hole in the centre of each lid.
Stack three lids on the left peg, largest at the bottom, and move the tower to the right peg in as few moves as you can. Count the moves.
Try again until you reach 7 moves, and write down the sequence of moves.
Add a fourth lid and solve it in 15 moves. Notice that the first 7 moves put the top three lids on the middle peg.
Record the least moves for 1, 2, 3, 4 and 5 lids, and show that each is double the previous plus one.
Time how long 5 lids take at one move per second: 31 seconds. Calculate how long 20 lids would take at that rate: more than 12 days.
Write the rule 2 to the n minus 1 on the board with a table up to 10 discs (1,023 moves).
Add a tip for visitors: on an odd number of discs, move the smallest disc to the target peg first; on an even number, to the spare peg.
What you should see
The towers are solved in 1, 3, 7, 15 and 31 moves for 1 to 5 lids, matching 2 to the n minus 1, and the timing shows how fast the puzzle grows.
Viva questions
A teacher or a judge will ask how it works. Try to answer each question before you open it, then compare.
1What is the minimum number of moves for 6 discs?
63.
2Why is the number of moves doubled plus one?
You move the smaller tower twice, once out of the way and once back, plus one move for the largest disc.
3What is the rule for which disc to move first?
The smallest disc always moves first; it goes to the target peg if the number of discs is odd, and to the spare peg if even.
4What does recursion mean here?
Solving the puzzle for n discs by using the solution for n minus 1 discs.
Take it further
Write a short program or a flowchart for the recursive solution and let it print the moves for 4 discs.
Change one thing, measure what happens, and add a table or chart of your readings: that is what turns a model into your own investigation.
Free ebooks for this project
Science projects
Maths Working Models and Activities
Make maths visible: models for number, geometry, algebra and data
Science projects
Science Projects for Class 6 to 8
Working models matched to middle-school science topics