Five more problems
Five olympiad-style problems of ours, with complete proofs
These are standard olympiad exercises of the kind every training program uses, written up by us; none is taken from a past CMO, CJMO, COMC or IMO paper, and the proofs as written are ours. They cover the four areas olympiads draw on: number theory (above), combinatorics, algebra and geometry. Try each for twenty minutes before reading the proof.
Problem 2. A standard olympiad exercise, not from any CMS paper; the write-up is ours. Combinatorics: an invariant. The numbers 1, 2, 3, ..., 10 are written on a board. A move erases any two numbers a and b and writes the single number |a - b| in their place. After nine moves one number is left. Can that number be 0?
Proof that it cannot. Look at the sum of all the numbers on the board. A move replaces a + b by |a - b|. The difference between these, (a + b) - |a - b|, is twice the smaller of a and b, which is even. So every move changes the sum by an even amount, and the parity of the sum never changes. At the start the sum is 1 + 2 + ... + 10 = 55, which is odd. So the last number is odd, and in particular it is not 0. The idea, finding a quantity that never changes, is called an invariant, and it settles questions that look as though they need a search through every sequence of moves.
Problem 3. A standard olympiad exercise, not from any CMS paper; the write-up is ours. Combinatorics: pigeonhole. Five points are placed inside or on the boundary of a square of side 1. Prove that some two of them are at distance at most √2 / 2 from each other.
Proof. Divide the square into four smaller squares of side 1/2 by joining the midpoints of opposite sides. Every point of the large square lies in at least one small square (a point on a dividing line can be assigned to either). Five points and four small squares means some small square contains at least two of the points, by the pigeonhole principle. Two points in a square of side 1/2 are at most the length of its diagonal apart, which is √((1/2)2 + (1/2)2) = √2 / 2. So those two points are at distance at most √2 / 2.
Problem 4. A standard olympiad exercise, not from any CMS paper; the write-up is ours. Algebra: an inequality. Prove that for all positive real numbers a, b and c, (a + b)(b + c)(c + a) ≥ 8abc, and find when equality holds.
Proof. For positive x and y, (√x - √y)2 ≥ 0 expands to x + y ≥ 2√(xy). Apply this three times: a + b ≥ 2√(ab), b + c ≥ 2√(bc) and c + a ≥ 2√(ca). All six quantities are positive, so the inequalities may be multiplied: (a + b)(b + c)(c + a) ≥ 8√(a2b2c2) = 8abc. Equality in each step needs a = b, b = c and c = a, so equality holds exactly when a = b = c. Note the line about positivity: multiplying inequalities is only safe because every side is positive, and saying so is part of the proof.
Problem 5. A standard olympiad exercise, not from any CMS paper; the write-up is ours. Geometry: the angle bisector. In triangle ABC, the bisector of angle A meets BC at D. Prove that BD / DC = AB / AC.
Proof, by areas. Triangles ABD and ADC share the height from A to the line BC, so the ratio of their areas is BD / DC. Now compute the same areas a second way, using two sides and the included angle. Let the angle at A be 2t, so the bisector makes angle t with each of AB and AC. Then area(ABD) = (1/2)(AB)(AD)sin t and area(ADC) = (1/2)(AC)(AD)sin t, so their ratio is AB / AC. Both expressions are the ratio of the same two areas, so BD / DC = AB / AC. Computing one quantity in two ways is among the most useful ideas in olympiad geometry.
Problem 6. A standard olympiad exercise, not from any CMS paper; the write-up is ours. Algebra: a functional equation. Find all functions f from the real numbers to the real numbers such that f(x + y) = f(x) + 2y for all real x and y.
Solution. Put x = 0: f(y) = f(0) + 2y for every real y. Writing c = f(0), any solution must be f(x) = 2x + c. Conversely, if f(x) = 2x + c for a constant c, then f(x + y) = 2x + 2y + c and f(x) + 2y = 2x + c + 2y, which are equal. So the solutions are exactly the functions f(x) = 2x + c, for any real constant c. The second half, checking that the candidates really work, is the step students most often leave out, and on an olympiad it is part of the answer.
Using the set
Spend twenty minutes on each problem before reading the proof, then write your own proof from memory the next day. The second write-up is where the learning happens.
Problems 2 and 3 suit a strong Grade 8 or 9 student. Problems 4 to 6 suit students already writing the COMC.
Six ideas worth naming
Reduce to primes. Find an invariant. Use pigeonhole. Combine simple inequalities. Compute one thing two ways. Substitute, then check.
Olympiad training is largely the collection of ideas like these, practised until a student reaches for the right one without being told.
