40th International Mathematical Olympiad 1999 Problems & Solutions

A1.  Find all finite sets S of at least three points in the plane such that for all distinct points A, B in S, the perpendicular bisector of AB is an axis of symmetry for S.

A2.  Let n ≥ 2 be a fixed integer. Find the smallest constant C such that for all non-negative reals x₁, ... , x_n:   ∑_i<j x_i x_j (x_i² + x_j²) ≤ C ( ∑ x_i )⁴.

Determine when equality occurs.

A3.  Given an n x n square board, with n even. Two distinct squares of the board are said to be adjacent if they share a common side, but a square is not adjacent to itself. Find the minimum number of squares that can be marked so that every square (marked or not) is adjacent to at least one marked square.

B1.  Find all pairs (n, p) of positive integers, such that: p is prime; n ≤ 2p; and (p - 1)ⁿ + 1 is divisible by n^p-1.

B2.  The circles C₁ and C₂ lie inside the circle C, and are tangent to it at M and N, respectively. C₁ passes through the center of C₂. The common chord of C₁ and C₂, when extended, meets C at A and B. The lines MA and MB meet C₁ again at E and F. Prove that the line EF is tangent to C₂.

B3.  Determine all functions f: R→R such that f(x - f(y) ) = f( f(y) ) + x f(y) + f(x) - 1 for all x, y in R. [R is the reals.] 

Solutions

Problem A1

Find all finite sets S of at least three points in the plane such that for all distinct points A, B in S, the perpendicular bisector of AB is an axis of symmetry for S.

 

Solution

by Gerhard Woeginger

The possible sets are just the regular n-gons (n > 2).

Let A₁, A₂, ... , A_k denote the vertices of the convex hull of S (and take indices mod k as necessary). We show first that these form a regular k-gon. A_i+1 must lie on the perpendicular bisector of A_i and A_i+2 (otherwise its reflection would lie outside the hull). Hence the sides are all equal. Similarly, A_i+1 and A_i+2 must be reflections in the perpendicular bisector of A_i and A_i+3 (otherwise one of the reflections would lie outside the hull). Hence all the angles are equal.

Any axis of symmetry for S must also be an axis of symmetry for the A_i, and hence must pass through the center C of the regular k-gon. Suppose X is a point of S in the interior of k-gon. Then it must lie inside or on some triangle A_iA_i+1C. C must be the circumcenter of A_iA_i+1X (since it lies on the three perpendicular bisectors, which must all be axes of symmetry of S), so X must lie on the circle center C, through A_i and A_i+1. But all points of the triangle A_iA_i+1X lie strictly inside this circle, except A_iand A_i+1, so X cannot be in the interior of the k-gon.

Problem A2

Let n >= 2 by a fixed integer. Find the smallest constant C such that for all non-negative reals x₁, ... , x_n:

  ∑_i<j x_i x_j (x_i² + x_j²) <= C (∑ x_i)⁴.

Determine when equality occurs.

 

Answer Answer: C = 1/8. Equality iff two x_i are equal and the rest zero.

 

Solution

By a member of the Chinese team at the IMO - does anyone know who?

(∑ x_i)⁴ = (∑ x_i² + 2 ∑_i<jx_ix_j)² ≥ 4 (∑ x_i²) (2 ∑_i<j x_ix_j) = 8 ∑_i<j ( x_ix_j ∑ x_k²) ≥ 8 ∑_i<j x_ix_j(x_i² + x_j²).

The second inequality is an equality only if n - 2 of the x_i are zero. So assume that x₃ = x₄ = ... = x_n = 0. Then for the first inequality to be an equality we require that (x₁² + x₂²) = 2 x₁x₂ and hence that x₁ = x₂. However, that is clearly also sufficient for equality.

 

Alternative solution by Gerhard Woeginger

Setting x₁ = x₂ = 1, x_i = 0 for i > 2 gives equality with C = 1/8, so, C cannot be smaller than 1/8.

We now use induction on n. For n = 2, the inequality with C = 1/8 is equivalent to (x₁ - x₂)⁴ ≥ 0, which is true, with equality iff x₁ = x₂. So the result is true for n = 2.

For n > 2, we may take x₁ + ... + x_n = 1, and x₁ ≤ x₂ ≤ ... ≤ x_n. Now replace x₁ and x₂ by 0 and x₁ + x₂. The sum on the rhs is unchanged and the sum on the lhs is increased by (x₁ + x₂)³ S - (x₁³ + x₂³) S - x₁x₂(x₁² + x₂²), where S = x₃ + x₄ + ... + x_n. But S is at least 1/3 (the critical case is n = 3, x_i = 1/3), so this is at least x₁x₂(x₁ + x₂ - x₁² - x₂²). This is strictly greater than 0 unless x₁ = 0 (when it equals 0), so the result follows by induction.

 

Comment. The first solution is elegant and shows clearly why the inequality is true. The second solution is more plodding, but uses an approach which is more general and can be applied in many other cases. At least with hindsight, the first solution is not as impossible to find as one might think. A little playing around soon uncovers the fact that one can get C = 1/8 with two x_i equal and the rest zero, and that this looks like the best possible. One just has to make the jump to replacing (x_i² + x_j²) by ∑ x_k². The solution is then fairly clear. Of course, that does not detract from the contestant's achievement, because I and almost everyone else who has looked at the problem failed to make that jump.

Problem A3

Given an n x n square board, with n even. Two distinct squares of the board are said to be adjacent if they share a common side, but a square is not adjacent to itself. Find the minimum number of squares that can be marked so that every square (marked or not) is adjacent to at least one marked square.

 

Answer

Answer: n/2 (n/2 + 1) = n(n + 2)/4.

 

Solution

Let n = 2m. Color alternate squares black and white (like a chess board). It is sufficient to show that m(m+1)/2 white squares are necessary and sufficient to deal with all the black squares.

This is almost obvious if we look at the diagonals.

Look first at the odd-length white diagonals. In every other such diagonal, mark alternate squares (starting from the border each time, so that r+1 squares are marked in a diagonal length 2r+1). Now each black diagonal is adjacent to a picked white diagonal and hence each black square on it is adjacent to a marked white square. In all 1 + 3 + 5 + ... + m-1 + m + m-2 + ... + 4 + 2 = 1 + 2 + 3 + ... + m = m(m+1)/2 white squares are marked. This proves sufficiency.

For necessity consider the alternate odd-length black diagonals. Rearranging, these have lengths 1, 3, 5, ... , 2m-1. A white square is only adjacent to squares in one of these alternate diagonals and is adjacent to at most 2 squares in it. So we need at least 1 + 2 + 3 + ... + m = m(m+1)/2 white squares. 

Problem B1

Find all pairs (n, p) of positive integers, such that: p is prime; n ≤ 2p; and (p - 1)ⁿ + 1 is divisible by n^p-1.

 

Answer

(1, p) for any prime p; (2, 2); (3, 3).

 

Solution

by Gerhard Woeginger, Technical University, Graz

Answer: (1, p) for any prime p; (2, 2); (3, 3).

Evidently (1, p) is a solution for every prime p. Assume n > 1 and take q to be the smallest prime divisor of n. We show first that q = p.

Let x be the smallest positive integer for which (p - 1)^x = - 1 (mod q), and y the smallest positive integer for which (p - 1)^y = 1 (mod q). Certainly y exists and indeed y < q, since (p - 1)^q-1 = 1 (mod q). We know that (p - 1)ⁿ = -1 (mod q), so x exists also. Writing n = sy + r, with 0 ≤ r < y, we conclude that (p - 1)^r = -1 (mod q), and hence x ≤ r < y (r cannot be zero, since 1 is not -1 (mod q) ).

Now write n = hx + k with 0 ≤ k < x. Then   -1 = (p - 1)ⁿ = (-1)^h(p - 1)^k (mod q). h cannot be even, because then (p - 1)^k = -1 (mod q), contradicting the minimality of x. So h is odd and hence (p - 1)^k = 1 (mod q) with 0 ≤ k < x < y. This contradicts the minimality of y unless k = 0, so n = hx. But x < q, so x = 1. So (p - 1) = -1 (mod q). p and q are primes, so q = p, as claimed.

So p is the smallest prime divisor of n. We are also given that n ≤ 2p. So either p = n, or p = 2, n = 4. The latter does not work, so we have shown that n = p. Evidently n = p = 2 and n = p = 3 work. Assume now that p > 3. We show that there are no solutions of this type.

Expand (p - 1)^p + 1 by the binomial theorem, to get (since (-1)^p = -1): 1 + -1 + p² - 1/2 p(p - 1)p² + p(p - 1)(p - 2)/6 p³ - ...
The terms of the form (bin coeff) pⁱ with i >= 3 are obviously divisible by p³, since the binomial coefficients are all integral. Hence the sum is p² + a multiple of p³. So the sum is not divisible by p³. But for p > 3, p^p-1 is divisible by p³, so it cannot divide (p - 1)^p + 1, and there are no more solutions. 

Problem B2

The circles C₁ and C₂ lie inside the circle C, and are tangent to it at M and N, respectively. C₁ passes through the center of C₂. The common chord of C₁ and C₂, when extended, meets C at A and B. The lines MA and MB meet C₁ again at E and F. Prove that the line EF is tangent to C₂.

 

Solution

Solution by Jean-Pierre Ehrmann

Let O, O₁, O₂ and r, r₁, r₂ be the centers and radii of C, C₁, C₂ respectively. Let EF meet the line O₁O₂ at W, and let O₂W = x. We need to prove that x = r₂.

Take rectangular coordinates with origin O₂, x-axis O₂O₁, and let O have coordinates (a, b). Notice that O and M do not, in general, lie on O₁O₂. Let AB meet the line O₁O₂ at V.

We observe first that O₂V = r₂²/(2 r₁). [For example, let X be a point of intersection of C₁ and C₂ and let Y be the midpoint of O₂X. Then O₁YO₂ and XVO₂ are similar. Hence, O₂V/O₂X = O₂Y/O₂O₁.]

An expansion (or, to be technical, a homothecy) center M, factor r/r₁ takes O₁ to O and EF to AB. Hence EF is perpendicular to O₁O₂. Also the distance of O₁ from EF is r₁/r times the distance of O from AB, so (r₁ - x) = r₁/r (a - r₂²/(2 r₁) ) (*).

We now need to find a. We can get two equations for a and b by looking at the distances of O from O₁ and O₂. We have:
  (r - r₁)² = (r₁ - a)² + b², and
  (r - r₂)² = a² + b².

Subtracting to eliminate b, we get   a = r₂²/(2 r₁) + r - r r₂/r₁.   Substituting back in (*), we get x = r₂, as required.

Alternative solution by Marcin Kuczma, communicated Arne Smeets

Let C₁ and C₂ meet at X and Y, and let AN meet C₂ again at D. Then AE·AM = AX·AY = AD·AN, so triangles AED and ANM are similar. Hence ∠ADE = ∠AMN.

Take the tangent AP as shown. Then ∠PAN = ∠AMN = ∠ADE, so AP and DE are parallel. The homothecy center M mapping C to C₁ takes the line AP to the line ED, so ED is tangent to C₁ at E. A similar argument show that it is tangent to C₂ at D. The homothecy takes AB to EF, so EF is perpendicular to O₁O₂ (the line of centers). Hence O₂EF is isosceles. So angle O₂EF = angle O₂FE = angle DEO₂ (DE tangent). In other words, O₂E bisects angle DEF. But ED is tangent to C₂, so EF is also.

 Problem 6

Determine all functions f: R -> R such that f(x - f(y) ) = f( f(y) ) + x f(y) + f(x) - 1 for all x, y in R. [R is the reals.]

 

Solution

Solution communicated by Ong Shien Jin

Let c = f(0) and A be the image f(R). If a is in A, then it is straightforward to find f(a): putting a = f(y) and x = a, we get f(a - a) = f(a) + a² + f(a) - 1, so f(a) = (1 + c)/2 - a²/2 (*).

The next step is to show that A - A = R. Note first that c cannot be zero, for if it were, then putting y = 0, we get: f(x - c) = f(c) + xc + f(x) - 1 (**) and hence f(0) = f(c) = 1. Contradiction. But (**) also shows that f(x - c) - f(x) = xc + (f(c) - 1). Here x is free to vary over R, so xc + (f(c) - 1) can take any value in R.

Thus given any x in R, we may find a, b in A such that x = a - b. Hence f(x) = f(a - b) = f(b) + ab + f(a) - 1. So, using (*):   f(x) = c - b²/2 + ab - a²/2 = c - x²/2.

In particular, this is true for x in A. Comparing with (*) we deduce that c = 1. So for all x in R we must have   f(x) = 1 - x²/2. Finally, it is easy to check that this satisfies the original relation and hence is the unique solution.