Why puzzles and games matter in maths
People have played with numbers for thousands of years. Many puzzles were just for fun. But some of them showed a new idea, and the idea became real maths.
- Magic squares appear in old Chinese and Indian writing. They led to ideas about patterns in numbers.
- The Konigsberg bridge puzzle (1736) made Euler think about dots and lines. This started graph theory, which is used in maps and the internet.
- The Tower of Hanoi (1883) is a clean example of recursion: a big job solved by using a smaller copy of the same job.
- Nim is a game that can be won by a rule. This is the start of game theory.
So puzzles are a safe way to practise maths thinking: look for a pattern, test it, then prove it.
The Tower of Hanoi
You have 3 pegs and n disks of different sizes. All disks start on the first peg, biggest at the bottom. Goal: move all disks to the last peg.
Rules: (1) move only one disk at a time; (2) take only the top disk of a peg; (3) never put a bigger disk on a smaller disk.
Look at small cases first:
| Disks | Least moves |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
Do you see the pattern? Each number is double the one before, plus 1. Every number is also one less than a power of 2: 1 = 2¹-1, 3 = 2²-1, 7 = 2³-1, 15 = 2⁴-1.
Why 2^n - 1? The doubling idea
To move n disks from peg A to peg C, you must do three jobs:
- Move the top n - 1 disks from A to B (to get them out of the way).
- Move the biggest disk from A to C (1 move).
- Move the n - 1 disks from B to C, on top of the big disk.
Jobs 1 and 3 are the same smaller puzzle. So if T(n) is the least number of moves:
T(n) = 2 × T(n - 1) + 1, with T(1) = 1.
This gives 1, 3, 7, 15, 31, 63 and so on. The closed form is T(n) = 2n - 1. Using a smaller copy of the same problem is called recursion.
A famous story says monks move 64 gold disks. That needs 264 - 1 moves, about 18 quintillion. Even one move every second would take over 500 billion years.
The game of Nim
Take a pile of 21 sticks. Two players take turns. On a turn you remove 1, 2 or 3 sticks. The player who takes the last stick wins.
Secret: if you leave a multiple of 4 (20, 16, 12, 8, 4), you win. Why? Whatever your opponent takes (1, 2 or 3), you take the rest of that block of 4 (3, 2 or 1). So the pile always drops by 4 per round, and you reach 0 first.
So with 21 sticks, the first player takes 1 and leaves 20, then keeps the pile on a multiple of 4. If the starting pile is already a multiple of 4, the second player wins with perfect play.
Magic squares
A magic square is a square grid of different numbers where every row, every column and both diagonals have the same sum, called the magic constant.
For the numbers 1 to n² in an n by n square, the constant is n(n² + 1) / 2. For a 3 by 3 square it is 3 × 10 / 2 = 15. For 4 by 4 it is 4 × 17 / 2 = 34.
Why 15? The numbers 1 to 9 add to 45. Three equal rows share 45, so each row is 45 / 3 = 15. The middle number must be 5 (the average). A 3 by 3 example:
| 2 | 7 | 6 |
| 9 | 5 | 1 |
| 4 | 3 | 8 |
This pattern is known from ancient China as the Lo Shu square. Magic squares were studied in India too, including a famous 4 by 4 square carved at Khajuraho.
A bridge puzzle that began graph theory
The old city of Konigsberg had 7 bridges joining 4 pieces of land. Could a person walk over every bridge exactly once? In 1736 Leonhard Euler said no.
He drew each piece of land as a dot and each bridge as a line. A walk that uses every line once only works if at most 2 dots have an odd number of lines. Here all 4 dots had an odd number, so it was impossible. This one idea began graph theory.
Try it: solve it yourself
- In the 3D, set the slider to 2 disks. Play it by tapping. Can you do it in 3 moves?
- Predict the least moves for 4 disks. Then solve it and check the counter.
- At home, use 3 coins of different sizes for 3 disks, and 3 plates for pegs. Solve it in 7 moves.
- Play Nim with a friend using 21 pencils. Try the "leave a four" rule.
Key formulas and definitions
- Tower of Hanoi: least moves for n disks = 2^n - 1
- Recursion: T(n) = 2 x T(n - 1) + 1, with T(1) = 1
- Magic constant for an n by n square (numbers 1 to n^2) = n(n^2 + 1) / 2
- Nim (take 1 to 3, last stick wins): leave a multiple of 4
- Euler walk over every line once: allowed only if at most 2 dots have an odd number of lines
Worked examples
1. How many least moves does the Tower of Hanoi need for 5 disks?
T(n) = 2^n - 1. For n = 5: 2^5 - 1 = 32 - 1 = 31 moves. Check with doubling: 15 x 2 + 1 = 31.
2. A pile has 17 sticks. You take 1, 2 or 3 per turn, and taking the last stick wins. You go first. What do you take?
Leave a multiple of 4. 17 - 1 = 16, so take 1. After that, whatever your friend takes (k), you take 4 - k.
3. Find the magic constant of a 5 by 5 magic square using the numbers 1 to 25.
n(n^2 + 1) / 2 = 5 x (25 + 1) / 2 = 5 x 26 / 2 = 65.
4. In a 3 by 3 magic square (constant 15), the first row is 8, ?, 6 and the middle number is 5. Find the missing number.
Row sum is 15, so ? = 15 - 8 - 6 = 1. Check the column through the middle: 1 + 5 + 9 = 15, so the bottom is 9.
5. A robot makes 1 Hanoi move per second. How long does it take for 8 disks?
Moves = 2^8 - 1 = 255. At 1 per second that is 255 seconds, about 4 minutes 15 seconds.
6. Show how to move 2 disks from peg A to peg C in 3 moves.
Move 1: small disk A to B. Move 2: big disk A to C. Move 3: small disk B to C. That equals 2^2 - 1 = 3.
Common mistakes
- Thinking the moves for n disks are 2n or n^2. Check: 3 disks need 7, not 6 or 9. The rule is 2^n - 1.
- Putting a big disk on a small one even for one move. That breaks the main rule.
- Leaving the pile at a wrong number in Nim. Count the sticks left after your move, not before.
- Forgetting that every row, column AND both diagonals must give the same magic sum.