BTT Mathematics / Primary Mathematics Learning Hub / Tower of Hanoi
The Tower of Hanoi is a small puzzle with a large mathematical idea: a difficult problem can be solved by reducing it to a smaller version of the same problem. That repeated self-reference is called recursion.
The standard puzzle has three pegs and n disks of different sizes. All disks begin stacked on one peg, largest at the bottom. A legal move transfers exactly one top disk to another peg, and a larger disk may never be placed on a smaller disk.
The goal is to move the complete stack to a target peg. For n disks, the minimum number of moves is
T(n)=2n−1.
The formula is not a lucky pattern. To move the largest disk, every smaller disk must first be moved out of its way. That requires solving an (n−1)-disk Tower of Hanoi problem. Then the largest disk moves once. Finally the (n−1)-disk stack must be moved back on top of it. Therefore
T(n)=T(n−1)+1+T(n−1)=2T(n−1)+1.
This guide is Primary Mathematics enrichment. It connects Working Backwards and Reverse Processes, Algorithms, Flowcharts and Decision Trees, Regularity in Repeated Reasoning and Route Networks.
The puzzle is optional enrichment, not a universal Primary syllabus requirement. Use the MOE Primary curriculum page and the learner’s school programme for required scope.
Rules and states · Recursive structure · Minimum-move proof · State transitions · How often each disk moves · 24 questions · Worked answers
1. A state records where every disk is
A state tells us which peg contains each disk. Because disks on a peg must always appear largest-to-smallest from bottom to top, specifying the peg of every disk completely determines the legal stack arrangement.
Worked example A: Two disks
With two disks and three pegs, each disk can be on any of three pegs. There are 3²=9 legal states. Some states place both disks on one peg; others separate them.
Worked example B: Three disks
There are 3³=27 legal states. The start state and target state are only two vertices in a larger state network.
Worked example C: What makes a transition legal?
A legal transition changes the peg of exactly one disk, and that disk must be exposed at the top of its current peg. Its destination must be empty or topped by a larger disk.
Worked example D: One move is one edge
If states are drawn as vertices of a graph, each legal move becomes an edge joining two states. A Tower solution is therefore a path through the state graph.
2. The full problem contains two smaller copies of itself
Let disks be numbered from 1 (smallest) to n (largest). To move disk n from source peg A to target peg C, disks 1 through n−1 must first be moved from A to the spare peg B. That is exactly the same kind of puzzle with one fewer disk.
Worked example E: Three disks
First move the top two disks from A to B in 3 moves. Move disk 3 from A to C in 1 move. Move the two-disk stack from B to C in 3 moves. Total=7 moves.
Worked example F: Four disks
T(4)=2T(3)+1=2×7+1=15.
Worked example G: Five disks
T(5)=2×15+1=31.
Recursive procedure
To move n disks from A to C using B:
1. Move n−1 disks from A to B using C.
2. Move disk n from A to C.
3. Move n−1 disks from B to C using A.
The same three-step instruction is applied again inside steps 1 and 3 until the base case n=1 is reached.
3. Why 2ⁿ−1 is a minimum, not just one possible count
To prove a solution is optimal, we need a lower bound and a construction that meets it.
Lower bound
Before the largest disk can move, all n−1 smaller disks must be removed from its peg. Under the same rules, that requires at least T(n−1) moves. The largest disk then requires one move. Afterward the n−1 smaller disks must be assembled on top of it, requiring at least another T(n−1) moves.
So every solution needs at least 2T(n−1)+1 moves.
Construction
The recursive procedure actually completes the task in exactly 2T(n−1)+1 moves. Therefore the lower bound is attained and is the true minimum.
Worked example H: Derive the powers of two
T(1)=1.
T(2)=2×1+1=3.
T(3)=2×3+1=7.
T(4)=2×7+1=15.
T(5)=31.
Each value is one less than 2,4,8,16,32. Therefore the pattern is T(n)=2ⁿ−1.
Worked example I: Reverse the formula
If an optimal solution uses31 moves, solve 2ⁿ−1=31. Then2ⁿ=32, so n=5.
4. State transitions turn the puzzle into a shortest-path problem
The state graph contains every legal configuration. Two states are adjacent when one legal move changes one into the other. The minimum Tower solution is a shortest path from the all-on-source state to the all-on-target state.
Worked example J: Two-disk state path
Starting A,A and targeting C,C, one shortest route is:
(A,A) → (B,A) → (B,C) → (C,C),
where the ordered pair records the pegs of disk1 and disk2. This uses 3 transitions.
Worked example K: Not every apparent move is an edge
From a state with disk1 on top of disk2, disk2 cannot move until disk1 leaves. A state change that relocates disk2 directly is not adjacent in the legal state graph.
Worked example L: Reversibility
Every legal Tower move can be reversed immediately: if a smaller disk can be placed on a larger disk or empty peg, moving it back is also legal. Thus the state graph is undirected under the standard rules.
Worked example M: Number of legal states
With n labelled disks and three pegs, there are 3ⁿ legal states. The shortest solution visits only a carefully structured subset of them.
5. In an optimal solution, smaller disks move more often
In the standard minimum solution, disk k, where disk1 is smallest and diskn is largest, moves
2n−k times.
Worked example N: Four disks
Disk1 moves8 times, disk2 moves4 times, disk3 moves2 times and disk4 moves1 time. Total=8+4+2+1=15.
Worked example O: Five disks
Move counts are16,8,4,2,1. Their sum is31.
Worked example P: Largest disk
The largest disk moves exactly once in every optimal standard solution: after all smaller disks are moved aside and before they are rebuilt on top.
Worked example Q: Before and after the largest move
For n=4, exactly T(3)=7 moves are needed before disk4 moves, then one move for disk4, then7 after. This 7+1+7 split makes the recursive symmetry visible.
Worked example R: Smallest disk
For n=6, the smallest disk moves2⁵=32 times in the standard optimal solution, while the largest moves once.
6. Practice: 24 original questions
Questions 1–8: Minimum moves and recurrence
1. What is T(1)?
2. What is T(2)?
3. What is T(3)?
4. What is T(4)?
5. What is T(5)?
6. Use T(3)=7 to calculate T(4) from the recurrence.
7. Use T(n)=2ⁿ−1 to find T(6).
8. An optimal solution uses127 moves. How many disks are there?
Questions 9–16: Recursive structure and disk moves
9. For four disks, how many moves occur before the largest disk moves?
10. How many occur after it moves?
11. In an optimal four-disk solution, how many times does disk1 move?
12. Disk2?
13. Disk3?
14. Disk4?
15. Check that the four disk-move counts sum to T(4).
16. In an optimal six-disk solution, how many times does the smallest disk move?
Questions 17–24: States and transitions
17. How many legal states exist with two disks and three pegs?
18. How many with three disks?
19. How many with four disks?
20. What must change between two adjacent states in the standard state graph?
21. Why can the largest disk not move first when n>1?
22. Is every legal transition reversible?
23. What graph-theory problem is equivalent to finding the minimum Tower solution?
24. Explain why proving a lower bound and constructing a solution that reaches it establishes optimality.
7. Worked answers
Answers 1–8
1. 1.
2. 3.
3. 7.
4. 15.
5. 31.
6. 15. 2×7+1.
7. 63. 2⁶−1.
8. 7 disks. 127+1=128=2⁷.
Answers 9–16
9. 7 moves. Move the top three aside.
10. 7 moves. Rebuild the top three on the target.
11. 8 times.
12. 4 times.
13. 2 times.
14. 1 time.
15. 8+4+2+1=15=T(4).
16. 32 times. 2⁵.
Answers 17–24
17. 9 states. 3².
18. 27 states. 3³.
19. 81 states. 3⁴.
20. Exactly one top disk changes peg, and the destination placement must remain legal.
21. Smaller disks are stacked above it and must first be moved away.
22. Yes. Under the standard rules, reversing a legal single-disk move is legal.
23. A shortest-path problem in the legal-state graph.
24. The lower bound says no solution can use fewer moves; the construction shows that many moves are actually sufficient. Therefore the bound is exact.
8. Teaching and transfer
If a learner memorizes 2ⁿ−1 without understanding, hide the formula and ask what must happen immediately before the largest disk can move. The recursive necessity becomes visible before the algebra.
When recursion feels circular
Use a base case. One disk is solved directly. The two-disk problem calls the already-understood one-disk problem; the three-disk problem calls the two-disk problem. Each recursive call is smaller.
When a learner counts one solution but cannot prove it is shortest
Separate “I found a route” from “no shorter route exists.” The lower-bound argument around the largest disk provides the missing proof.
When state graphs feel abstract
Write each state as a short peg code such as (A,B,C). A legal move changes one entry only, subject to top-disk legality.
When exponential growth is underestimated
Compare T(10)=1023 with T(20)=1,048,575. Adding disks increases difficulty multiplicatively, not additively.
Connect to repeated reasoning
The same three-step solution pattern repeats at every scale. That makes the Tower a concrete bridge from repeated reasoning to recursion and algorithmic decomposition.
Continue through this enrichment collection
For adjacency constraints, use Graph Coloring, Chromatic Number and Map Constraints. For nearest-region geometry, use Voronoi Diagrams, Nearest Regions and Geometric Partitioning. For repeated local update rules, use Cellular Automata, Local Rules and Emergent Patterns.
Return to the BTT Primary Mathematics Learning Hub.
Original enrichment guide with 24 original practice questions and separate worked answers. The minimum-move claims assume the standard three-peg Tower of Hanoi rules.