23rd International Mathematical Olympiad 1982 Problems & Solutions

A1.  The function f(n) is defined on the positive integers and takes non-negative integer values. f(2) = 0, f(3) > 0, f(9999) = 3333 and for all m, n:       f(m+n) - f(m) - f(n) = 0 or 1.

Determine f(1982).

A2.  A non-isosceles triangle A₁A₂A₃ has sides a₁, a₂, a₃ with a_i opposite A_i. M_i is the midpoint of side a_i and T_i is the point where the incircle touches side a_i. Denote by S_i the reflection of T_i in the interior bisector of angle A_i. Prove that the lines M₁S₁, M₂S₂ and M₃S₃ are concurrent.

A3.  Consider infinite sequences {x_n} of positive reals such that x₀ = 1 and x₀ ≥ x₁ ≥ x₂ ≥ ... . (a)  Prove that for every such sequence there is an n ≥ 1 such that:

      x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n ≥ 3.999.

(b)  Find such a sequence for which:

      x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n < 4   for all n.

B1.  Prove that if n is a positive integer such that the equation       x³ - 3xy² + y³ = n

has a solution in integers x, y, then it has at least three such solutions. Show that the equation has no solutions in integers for n = 2891.

B2.  The diagonals AC and CE of the regular hexagon ABCDEF are divided by inner points M and N respectively, so that:       AM/AC = CN/CE = r.

Determine r if B, M and N are collinear.

B3.  Let S be a square with sides length 100. Let L be a path within S which does not meet itself and which is composed of line segments A₀A₁, A₁A₂, A₂A₃, ... , A_n-1A_n with A₀ = A_n. Suppose that for every point P on the boundary of S there is a point of L at a distance from P no greater than 1/2. Prove that there are two points X and Y of L such that the distance between X and Y is not greater than 1 and the length of the part of L which lies between X and Y is not smaller than 198. 

Solutions

Problem A1

The function f(n) is defined on the positive integers and takes non-negative integer values. f(2) = 0, f(3) > 0, f(9999) = 3333 and for all m, n:

      f(m+n) - f(m) - f(n) = 0 or 1.

Determine f(1982).

 

Solution

We show that f(n) = [n/3] for n <= 9999, where [ ] denotes the integral part.

We show first that f(3) = 1. f(1) must be 0, otherwise f(2) - f(1) - f(1) would be negative. Hence f(3) = f(2) + f(1) + 0 or 1 = 0 or 1. But we are told f(3) > 0, so f(3) = 1. It follows by induction that f(3n) ≥ n. For f(3n+3) = f(3) + f(3n) + 0 or 1 = f(3n) + 1 or 2. Moreover if we ever get f(3n) > n, then the same argument shows that f(3m) > m for all m > n. But f(3.3333) = 3333, so f(3n) = n for all n <= 3333.

Now f(3n+1) = f(3n) + f(1) + 0 or 1 = n or n + 1. But 3n+1 = f(9n+3) ≥ f(6n+2) + f(3n+1) ≥ 3f(3n+1), so f(3n+1) < n+1. Hence f(3n+1) = n. Similarly, f(3n+2) = n. In particular f(1982) = 660. 

Problem A2

A non-isosceles triangle A₁A₂A₃ has sides a₁, a₂, a₃ with a_i opposite A_i. M_i is the midpoint of side a_i and T_i is the point where the incircle touches side a_i. Denote by S_i the reflection of T_i in the interior bisector of ∠A_i. Prove that the lines M₁S₁, M₂S₂ and M₃S₃ are concurrent.

 

Solution

Let B_i be the point of intersection of the interior angle bisector of the angle at A_i with the opposite side. The first step is to figure out which side of B_i T_i lies. Let A₁ be the largest angle, followed by A₂. Then T₂ lies between A₁ and B₂, T₃ lies between A₁ and B₃, and T₁ lies between A₂ and B₁. For ∠OB₂A₁ = 180^o - A₁ - A₂/2 = A₃ + A₂/2. But A₃ + A₂/2 < A₁ + A₂/2 and their sum is 180^o, so A₃ + A₂/2 < 90^o. Hence T₂ lies between A₁ and B₂. Similarly for the others.

Let O be the center of the incircle. Then ∠T₁OS₂ = ∠T₁OT₂ - 2 ∠T₂OB₂ = 180^o - A₃ - 2(90^o - ∠OB₂T₂) = 2(A₃ + A₂/2) - A₃ = A₂ + A₃. A similar argument shows ∠T₁OS₃ = A₂ + A₃. Hence S₂S₃ is parallel to A₂A₃.

Now ∠T₃OS₂ = 360^o - ∠T₃OT₁ - ∠T₁OS₂ = 360^o - (180^o - A₂) - (A₂ + A₃) = 180^o - A₃ = A₁ + A₂. ∠T₃OS₁ = ∠T₃OT₁ + 2 ∠T₁OB₁ = (180^o - A₂) + 2(90^o - ∠OB₁T₁) = 360^o - A₂ - 2(A₃ + A₁/2) = 2(A₁ + A₂ + A₃) - A₂ - 2A₃ - A₁ = A₁ + A₂ = ∠T₃OS₂. So S₁S₂ is parallel to A₁A₂. Similarly we can show that S₁S₃ is parallel to A₁A₃.

So S₁S₂S₃ is similar to A₁A₂A₃ and turned through 180^o. But M₁M₂M₃ is also similar to A₁A₂A₃ and turned through 180^o. So S₁S₂S₃ and M₁M₂M₃ are similar and similarly oriented. Hence the lines through corresponding vertices are concurrent. 

Problem A3

Consider infinite sequences {x_n} of positive reals such that x₀ = 1 and x₀ ≥= x₁ ≥ x₂ ≥ ... .

(a)  Prove that for every such sequence there is an n ≥ 1 such that:

      x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n ≥ 3.999.

(b)  Find such a sequence for which:

      x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n < 4   for all n.

 

Solution

(a)  It is sufficient to show that the sum of the (infinite) sequence is at least 4. Let k be the greatest lower bound of the limits of all such sequences. Clearly k ≥ 1. Given any ε > 0, we can find a sequence {x_n} with sum less than k + ε. But we may write the sum as:

x₀²/x₁ + x₁( (x₁/x₁)²/(x₂/x₁) + (x₂/x₁)²/(x₃/x₁) + ... + (x_n/x₁)²/(x_n+1/x₁) + ... ).

The term in brackets is another sum of the same type, so it is at least k. Hence k + ε > 1/x₁ + x₁k. This holds for all ε > 0, and so k ≥ 1/x₁ + x₁k. But 1/x₁ + x₁k ≥ 2√k, so k ≥ 4.

(b)  Let x_n = 1/2ⁿ. Then x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n = 2 + 1 + 1/2 + ... + 1/2^n-2 = 4 - 1/2^n-2 < 4. 

Problem B1

Prove that if n is a positive integer such that the equation

      x³ - 3xy² + y³ = n

has a solution in integers x, y, then it has at least three such solutions. Show that the equation has no solutions in integers for n = 2891.

 

Solution

If x, y is a solution then so is y-x, -x. Hence also -y, x-y. If the first two are the same, then y = -x, and x = y-x = -2x, so x = y = 0, which is impossible, since n > 0. Similarly, if any other pair are the same.

2891 = 2 (mod 9) and there is no solution to x³ - 3xy² + y³ = 2 (mod 9). The two cubes are each -1, 0 or 1, and the other term is 0, 3 or 6, so the only solution is to have the cubes congruent to 1 and -1 and the other term congruent to 0. But the other term cannot be congruent to 0, unless one of x, y is a multiple of 3, in which case its cube is congruent to 0, not 1 or -1. 

Problem B2

The diagonals AC and CE of the regular hexagon ABCDEF are divided by inner points M and N respectively, so that:

      AM/AC = CN/CE = r.

Determine r if B, M and N are collinear.

 

Solution

For an inelegant solution one can use coordinates. The advantage of this type of approach is that it is quick and guaranteed to work! Take A as (0,√3), B as (1,√3), C as (3/2,√3/2, D as (1,0). Take the point X, coordinates (x,0), on ED. We find where the line BX cuts AC and CE. The general point on BX is (k + (1-k)x,k√3). If this is also the point M with AM/AC = r then we have: k + (1-k)x = 3r/2, k√3 = (1-r)√3 + r√3/2. Hence k = 1 - r/2, r = 2/(4-x). Similarly, if it is the point N with CN/CE = r, then k + (1-k)x = 3(1-r)/2, k√3 = (1-r)√3/2. Hence k = (1-r)/2 and r = (2-x)/(2+x). Hence for the ratios to be equal we require 2/(4-x) = (2-x)/(2+x), so x² - 8x + 4 = 0. We also have x < 1, so x = 4 - √12. This gives r = 1/√3.

A more elegant solution uses the ratio theorem for the triangle EBC. We have CM/MX XB/BE EN/NC = -1. Hence (1-r)/(r - 1/2) (-1/4) (1-r)/r = -1. So r = 1/√3. 

Problem B3

Let S be a square with sides length 100. Let L be a path within S which does not meet itself and which is composed of line segments A₀A₁, A₁A₂, A₂A₃, ... , A_n-1A_n with A₀ = A_n. Suppose that for every point P on the boundary of S there is a point of L at a distance from P no greater than 1/2. Prove that there are two points X and Y of L such that the distance between X and Y is not greater than 1 and the length of the part of L which lies between X and Y is not smaller than 198.

 

Solution

Let the square be A'B'C'D'. The idea is to find points of L close to a particular point of A'D' but either side of an excursion to B'.

We say L approaches a point P' on the boundary of the square if there is a point P on L with PP' ≤ 1/2. We say L approaches P' before Q' if there is a point P on L which is nearer to A₀ (the starting point of L) than any point Q with QQ' ≤ 1/2.

Let A' be the first vertex of the square approached by L. L must subsequently approach both B' and D'. Suppose it approaches B' first. Let B be the first point on L with BB' ≤ 1/2. We can now divide L into two parts L₁, the path from A₀ to B, and L₂, the path from B to A_n.

Take X' to be the point on A'D' closest to D' which is approached by L₁. Let X be the corresponding point on L₁. Now every point on X'D' must be approached by L₂ (and X'D' is non-empty, because we know that D' is approached by L but not by L₁). So by compactness X' itself must be approached by L₂. Take Y to be the corresponding point on L₂. XY ≤ XX' + X'Y ≤ 1/2 + 1/2 = 1. Also BB' ≤ 1/2, so XB ≥ X'B' - XX' - BB' ≥ X'B' - 1 ≥ A'B' - 1 = 99. Similarly YB ≥ 99, so the path XY ≥ 198.

Read more

 

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.