Olympiad problems use induction on boards, lines, puzzles and games. Split a 2k+1 board into four 2k
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
use induction on boards, lines and puzzles;
set up a recursion from the structure of a problem;
strengthen a statement so that the induction goes through.
Tiling a board with L-shaped pieces
An L-shaped piece covers three squares of a board: two in a row and one beside them. Take a 2n×2n board and remove any one square. Claim: the rest can always be covered by L-shaped pieces, with no overlaps.
Base case. For n=1, a 2×2 board with one square removed is exactly one L-shaped piece.
Step. Take a 2k+1×2k+1 board with one square removed. Cut it into four 2k×2k quarters. The removed square is in one quarter.
Put one L-shaped piece in the middle of the board so that it covers one square of each of the other three quarters, at their corners next to the centre.
Now each quarter is a 2k×2k board with exactly one square taken. By the hypothesis, each can be tiled.
The number of pieces is 34n−1, because each piece covers 3 of the 4n−1 squares.
An 8 by 8 board with one square, in row 3 and column 6 counted from the top left, marked with a black cross as removed. The other 63 squares are covered by 21 L-shaped pieces of three squares, each piece in its own colour. Thick lines divide the board into four 4 by 4 quarters, and the L-shaped piece at the centre covers one corner square of each of the three quarters that do not hold the removed square.
Lines in the plane
Draw n lines, no two parallel and no three through one point. How many regions do they make? With 0 lines there is 1 region. Line number k crosses each of the k−1 earlier lines once. The crossings cut it into k pieces, and each piece splits a region in two. So line k adds k regions:
R(k)=R(k−1)+k.
Induction then gives R(n)=1+(1+2+⋯+n)=2n2+n+2.
Four straight lines drawn across a square window, no two parallel and no three through one point. The regions they make are numbered 1 to 11. A caption says that the fourth line, drawn in red, crosses the three earlier lines and adds 4 regions.
A colouring. The regions made by any lines can be coloured black and white so that neighbours always differ. Add the lines one at a time. When a new line goes in, swap the two colours on one side of it and keep the other side. Neighbours along the new line now differ, and all old neighbours still differ.
The Tower of Hanoi
Three pegs, and n discs of different sizes on one peg, the largest at the bottom. A move takes the top disc of a peg to another peg, never onto a smaller disc. To move the whole tower:
move the top n−1 discs to the spare peg;
move the largest disc;
move the n−1 discs on top of it.
So H(n)=2H(n−1)+1 with H(1)=1, and induction proves H(n)=2n−1. Fewer moves are impossible: the largest disc must move at least once, and before that the other n−1 discs must all leave it.
When the step fails, strengthen
Course 2 proved ∑r21≤2−n1, a stronger claim than "<2". Olympiad problems often need this trick. Ask what extra fact would make the step work, and add it to the statement.
Another trick is to choose what to induct on. In a game you may induct on the number of coins, in a graph on the number of points, in a board on its side. Pick the quantity that gets smaller when you take one part of the problem away.
A third trick is forward and backward induction, used by Cauchy for the AM-GM inequality. Prove it for n=2, then from n to 2n, which covers every power of 2. Then show that the case n gives the case n−1. Together these reach every n.
Practise with new numbers
Try it in Python
The program tiles an 8×8 board with one square removed, in the way the proof does, and prints the pieces with numbers. Then it counts the Hanoi moves by the recursion.
Common mistakes
Losing the removed square. In the tiling step, the middle piece must avoid the quarter that already has the hole.
Counting crossings wrong. Line k crosses k−1 lines and so adds k regions, not k−1.
Proving only an upper bound. In Hanoi, also show that fewer moves are impossible.
Inducting on the wrong thing. Choose a quantity that gets smaller in the step.
Remember these
L-shaped tiling: cut into four quarters, one piece in the middle.
Lines: R(n)=2n2+n+2, since line k adds k regions.
Hanoi: H(n)=2n−1.
If the step fails, strengthen the claim or change what you induct on.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
How many L-shaped pieces cover a 4×4 board with one square removed?
How many regions do 5 lines in general position make?
Find H(4) from the recursion H(n)=2H(n−1)+1 with H(1)=1.
Why does a 2n×2n board with no square removed never have an L-shaped tiling?
In the colouring argument, why do two regions that meet along an old line still differ after the swap?
References
Arthur Engel, Problem-Solving Strategies, Chapter 8, The Induction Principle.
Richard Hammack, Book of Proof, third edition, Chapter 10, Mathematical Induction.
Enroll free in Induction in Algebra, Calculus and Olympiad Problems
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.