24th International Mathematical Olympiad 1983 Problems & Solutions

A1.  Find all functions f defined on the set of positive reals which take positive real values and satisfy:   f(x(f(y)) = yf(x) for all x, y; and f(x) → 0 as x → ∞.

A2.  Let A be one of the two distinct points of intersection of two unequal coplanar circles C₁ and C₂ with centers O₁ and O₂ respectively. One of the common tangents to the circles touches C₁ at P₁ and C₂ at P₂, while the other touches C₁ at Q₁ and C₂ at Q₂. Let M₁ be the midpoint of P₁Q₁ and M₂ the midpoint of P₂Q₂. Prove that ∠O₁AO₂ = ∠M₁AM₂.

A3.  Let a , b and c be positive integers, no two of which have a common divisor greater than 1. Show that 2abc - ab - bc - ca is the largest integer which cannot be expressed in the form xbc + yca + zab, where x, y, z are non-negative integers.

B1.  Let ABC be an equilateral triangle and E the set of all points contained in the three segments AB, BC and CA (including A, B and C). Determine whether, for every partition of E into two disjoint subsets, at least one of the two subsets contains the vertices of a right-angled triangle.

B2.  Is it possible to choose 1983 distinct positive integers, all less than or equal to 10⁵, no three of which are consecutive terms of an arithmetic progression?

B3.  Let a, b and c be the lengths of the sides of a triangle. Prove that     a²b(a - b) + b²c(b - c) + c²a(c - a) ≥ 0.

Determine when equality occurs. 

Solutions

Problem A1

Find all functions f defined on the set of positive reals which take positive real values and satisfy:

  f(x(f(y)) = yf(x) for all x, y; and f(x) → 0 as x → ∞.

 

Solution

If f(k) = 1, then f(x) = f(xf(k)) = kf(x), so k =1. Let y = 1/f(x) and set k = xf(y), then f(k) = f(xf(y)) = yf(x) = 1. Hence f(1) = 1 and f(1/f(x)) = 1/x. Also f(f(y)) = f(1f(y)) = y. Hence f(1/x) = 1/f(x). Finally, let z = f(y), so that f(z) = y. Then f(xy) = f(xf(z)) = zf(x) = f(x)f(y).

Now notice that f(xf(x)) = xf(x). Let k = xf(x). We show that k = 1. f(k²) = f(k)f(k) = k² and by a simple induction f(kⁿ) = kⁿ, so we cannot have k > 1, or f(x) would not tend to 0 as x tends to infinity. But f(1/k) = 1/k and the same argument shows that we cannot have 1/k > 1. Hence k = 1.

So the only such function f is f(x) = 1/x. 

Problem A2

Let A be one of the two distinct points of intersection of two unequal coplanar circles C₁ and C₂ with centers O₁ and O₂ respectively. One of the common tangents to the circles touches C₁ at P₁ and C₂ at P₂, while the other touches C₁ at Q₁ and C₂ at Q₂. Let M₁ be the midpoint of P₁Q₁ and M₂ the midpoint of P₂Q₂. Prove that ∠O₁AO₂ = ∠M₁AM₂.

 

Solution

Let P₁P₂ and O₁O₂ meet at O. Let OA meet C₂ again at A₂. O is the center of similitude for C₁ and C₂ so ∠M₁AO₁ = ∠M₂A₂O₂. Hence if we can show that ∠M₂AO₂ = ∠M₂A₂O₂, then we are home.

Let X be the other point of intersection of the two circles. The key is to show that A₂, M₂ and X are collinear, for then ∠M₂AO₂ = ∠M₂XO₂ (by reflection) and O₂A₂X is isosceles.

But since O is the center of similitude, M₂A₂ is parallel to M₁A, and by reflection ∠XM₂O = ∠AM₂O, so we need to show that triangle AM₁M₂ is isosceles. Extend XA to meet P₁P₂ at Y. Then YP₁² = YA.YX = YP₂², so YX is the perpendicular bisector of M₁M₂, and hence AM₁ = AM₂ as required. 

Problem A3

Let a , b and c be positive integers, no two of which have a common divisor greater than 1. Show that 2abc - ab - bc - ca is the largest integer which cannot be expressed in the form xbc + yca + zab, where x, y, z are non-negative integers.

 

Solution

We start with the lemma that bc - b - c is the largest number which cannot be written as mb + nc with m and n non-negative. [Proof: 0, c, 2c, ... , (b-1)c is a complete set of residues mod b. If r > (b-1)c - b, then r = nc (mod b) for some 0 ≤ n ≤ b-1. But r > nc - b, so r = nc + mb for some m ≥ 0. That proves that every number larger than bc - b - c can be written as mb + nc with m and n non-negative. Now consider bc - b - c. It is (b-1)c (mod b), and not congruent to any nc with 0 ≤ n < b-1. So if bc - b - c = mb + nc, then n ≥ b-1. Hence mb + nc ≥ nc ≥ (b-1)c > bc - b - c. Contradiction.]

0, bc, 2bc, ... , (a-1)bc is a complete set of residues mod a. So given N > 2abc - ab - bc - ca we may take xbc = N (mod a) with 0 <= x < a. But N - xbc > 2abc - ab - bc - ca - (a-1)bc = abc - ab - ca = a(bc - b - c). So N - xbc = ka, with k > bc - b - c. Hence we can find non-negative y, z so that k = zb + yc. Hence N = xbc + yca + zab.

Finally, we show that for N = 2abc - ab - bc - ca we cannot find non-negative x, y, z so that N = xbc + yca + zab. N = -bc (mod a), so we must have x = -1 (mod a) and hence x ≥ a-1. Similarly, y ≥ b-1, and z ≥ c-1. Hence xbc + yca + zab ≥ 3abc - ab - bc - ca > N. Contradiction. 

Problem B1

Let ABC be an equilateral triangle and E the set of all points contained in the three segments AB, BC and CA (including A, B and C). Determine whether, for every partition of E into two disjoint subsets, at least one of the two subsets contains the vertices of a right-angled triangle.

 

Solution

It does.

Suppose otherwise, that E is the disjoint union of e and e' with no right-angled triangles in either set. Take points X, Y, Z two-thirds of the way along BC, CA, AB respectively (so that BX/BC = 2/3 etc). Then two of X, Y, Z must be in the same set. Suppose X and Y are in e. Now YX is perpendicular to BC, so all points of BC apart from X must be in e'. Take W to be the foot of the perpendicular from Z to BC. Then B and W are in e', so Z must be in e. ZY is perpendicular to AC, so all points of AC apart from Y must be in e'. e' is now far too big. For example let M be the midpoint of BC, then AMC is in e' and right-angled. 

Problem B2

Is it possible to choose 1983 distinct positive integers, all less than or equal to 10⁵, no three of which are consecutive terms of an arithmetic progression?

 

Solution

We may notice that an efficient way to build up a set with no APs length 3 is as follows. Having found 2ⁿ numbers in {1, 2, ... , u_n} we add the same pattern starting at 2u_n, thus giving 2ⁿ⁺¹ numbers in {1, 2, ... , 3u_n-1}. If x is in the first part and y, z in the second part, then 2y is at least 4u_n, whereas x + z is less than 4u_n, so x, y, z cannot be an AP length 3. If x and y are in the first part, and z in the second part, then 2y is at most 2u_n, but x + z is more than 2u_n, so x, y, z cannot be an AP length 3. To start the process off, we have the 4 numbers 1, 2, 4, 5 in {1, 2, 3, 4, 5}. So u₂ = 5. This gives u₁₁ = 88574, in other words we can find 2048 numbers in the first 88574 with no AP length 3.

If we are lucky, we may notice that if we reduce each number in the set we have constructed by 1 we get the numbers which have no 2 when written base 3. This provides a neater approach. Take x, y, z with no 2 when written in base 3. Then 2y has only 0s and 2s when written base 3. But x + z only has no 1s if x = z. So x, y, z cannot form an AP length 3. Also there are 2¹¹ = 2048 numbers of this type with 11 digits or less and hence ≤ 11111111111₃ = 88573. 

Problem B3

Let a, b and c be the lengths of the sides of a triangle. Prove that

    a²b(a - b) + b²c(b - c) + c²a(c - a) ≥ 0.

Determine when equality occurs.

 

Solution

Put a = y + z, b = z + x, c = x + y. Then the triangle condition becomes simply x, y, z > 0. The inequality becomes (after some manipulation):

    xy³ + yz³ + zx³ ≥ xyz(x + y + z).

Applying Cauchy's inequality we get (xy³ + yz³ + zx³)(z + x + y) ≥ xyz(y + z + x)² with equality iff xy³/z = yz³/x = zx³/y. So the inequality holds with equality iff x = y = z. Thus the original inequality holds with equality iff the triangle is equilateral.

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.