29th International Mathematical Olympiad 1988 Problems & Solutions

A1.  Consider two coplanar circles of radii R > r with the same center. Let P be a fixed point on the smaller circle and B a variable point on the larger circle. The line BP meets the larger circle again at C. The perpendicular to BP at P meets the smaller circle again at A (if it is tangent to the circle at P, then A = P). (i)  Find the set of values of AB² + BC² + CA².

(ii)  Find the locus of the midpoint of BC.

A2.  Let n be a positive integer and let A₁, A₂, ... , A_2n+1 be subsets of a set B. Suppose that:

(i)  Each A_i has exactly 2n elements,

(ii)  The intersection of every two distinct A_i contains exactly one element, and

(iii)  Every element of B belongs to at least two of the A_i.

For which values of n can one assign to every element of B one of the numbers 0 and 1 in such a way that each A_i has 0 assigned to exactly n of its elements?

A3.  A function f is defined on the positive integers by: f(1) = 1; f(3) = 3; f(2n) = f(n), f(4n + 1) = 2f(2n + 1) - f(n), and f(4n + 3) = 3f(2n + 1) - 2f(n) for all positive integers n. Determine the number of positive integers n less than or equal to 1988 for which f(n) = n.

B1.  Show that the set of real numbers x which satisfy the inequality:   1/(x - 1) + 2/(x - 2) + 3/(x - 3) + ... + 70/(x - 70) ≥ 5/4

is a union of disjoint intervals, the sum of whose lengths is 1988.

B2.  ABC is a triangle, right-angled at A, and D is the foot of the altitude from A. The straight line joining the incenters of the triangles ABD and ACD intersects the sides AB, AC at K, L respectively. Show that the area of the triangle ABC is at least twice the area of the triangle AKL.

B3.  Let a and b be positive integers such that ab + 1 divides a² + b². Show that (a² + b²)/(ab + 1) is a perfect square. 

Solutions

Problem A1

Consider two coplanar circles of radii R > r with the same center. Let P be a fixed point on the smaller circle and B a variable point on the larger circle. The line BP meets the larger circle again at C. The perpendicular to BP at P meets the smaller circle again at A (if it is tangent to the circle at P, then A = P).

(i)  Find the set of values of AB² + BC² + CA².
(ii)  Find the locus of the midpoint of BC.

Solution

(i)  Let M be the midpoint of BC. Let PM = x. Let BC meet the small circle again at Q. Let O be the center of the circles. Since angle APQ = 90 degrees, AQ is a diameter of the small circle, so its length is 2r. Hence AP² = 4r² - 4x². BM² = R² - OM² = R² - (r² - x²). That is essentially all we need, because we now have: AB² + AC² + BC² = (AP² + (BM - x)²) + (AP² + (BM + x)²) + 4BM² = 2AP² + 6BM² + 2x² = 2(4r² - 4x²) + 6(R² - r² + x²) + 2x² = 6R² + 2r² , which is independent of x.

(ii)  M is the midpoint of BC and PQ since the circles have a common center. If we shrink the small circle by a factor 2 with P as center, then Q moves to M, and hence the locus of M is the circle diameter OP. 

Problem A2

Let n be a positive integer and let A₁, A₂, ... , A_2n+1 be subsets of a set B. Suppose that:
(i)  Each A_i has exactly 2n elements,
(ii)  The intersection of every two distinct A_i contains exactly one element, and
(iii)  Every element of B belongs to at least two of the A_i.
For which values of n can one assign to every element of B one of the numbers 0 and 1 in such a way that A_i has 0 assigned to exactly n of its elements?

Solution

Answer: n even.

Each of the 2n elements of A_i belongs to at least one other A_j because of (iii). But given another A_j it cannot contain more than one element of A_i because of (ii). There are just 2n other A_j available, so each must contain exactly one element of A_i. Hence we can strengthen (iii) to every element of B belongs to exactly two of the As.

This shows that the arrangement is essentially unique. We may call the element of B which belongs to A_i and A_j (i,j). Then A_i contains the 2n elements (i, j) with j not i.

|B| = 1/2 x no. of As x size of each A = n(2n+1). If the labeling with 0s and 1s is possible, then if we list all the elements in each A, n(2n+1) out of the 2n(2n+1) elements have value 0. But each element appears twice in this list, so n(2n+1) must be even. Hence n must be even.

Next part thanks to Stan Dolan

Label (i,j) 0 if j = i-n/2, i-(n/2 - 1), ... , i-1, i+1, i+2, ... , i+n/2 (working mod 2n+1 when necessary). This clearly has the required property.

My original solution was a pedestrian induction:

We show by induction that a labeling is always possible for n even. If n = 2, there is certainly a labeling. For example, we may assign 0 to (1,2), (1,3), (2,4), (3,5), (4,5). Now suppose we have a labeling for n. For n + 2, we label (i , j) 0 if it was labeled 0 for n or if it is:
    (i, 2n+2) or (i, 2n+3) for i = 1, 2, ... , n+1
    (i, 2n+4) or (i, 2n+5) for i = n+2, n+3, ... , 2n+1
    (2n+2, 2n+4), (2n+3, 2n+5), (2n+4,2n+5).
For i = 1, 2, ... n+1, A_i has n elements (i, j) labeled zero with j ≤ 2n+1 and also (i, 2n+2) and (i, 2n+3), giving n+2 in all. For i = n+2, n+3, ... , 2n+1, A_i has n elements (i, j) labeled zero with j ≤ 2n+1 and also (i, 2n+4) and (i, 2n+5), giving n+2 in all. A_2n+2 has the n+1 elements (i, 2n+2) with i <= n+1 and also (2n+2, 2n+4), giving n+2 in all. A_2n+3 has the n+1 elements (i, 2n+3) for i ≤ n+1 and also (2n+3, 2n+5), giving n+2 in all. A_2n+4 has the n elements (i, 2n+4) with n+2 ≤ i ≤ 2n+1 and also (2n+2, 2n+4) and (2n+4, 2n+5), giving n+2 in all. Finally A_2n+5 has the n elements (i, 2n+5) with n+2 ≤ i ≤ 2n+1 and also (2n+3, 2n+5) and (2n+4, 2n+5), giving n+2 in all. 

Problem A3

A function f is defined on the positive integers by: f(1) = 1; f(3) = 3; f(2n) = f(n), f(4n + 1) = 2f(2n + 1) - f(n), and f(4n + 3) = 3f(2n + 1) - 2f(n) for all positive integers n. Determine the number of positive integers n less than or equal to 1988 for which f(n) = n.

Solution

Answer: 92.

f(n) is always odd. If n = b_r+1b_r...b₂b₁b₀ in binary and n is odd, so that b_r+1 = b₀ = 1, then f(n) = b_r+1b₁b₂...b_rb₀. If n has r+2 binary digits with r > 0, then there are 2^[(r+1)/2] numbers with the central r digits symmetrical, so that f(n) = n (because we can choose the central digit and those lying before it arbitarily, the rest are then determined). Also there is one number with 1 digit (1) and one number with two digits (3) satisfying f(n) = 1. So we find a total of 1 + 1 + 2 + 2 + 4 + 4 + 8 + 8 + 16 + 16 = 62 numbers in the range 1 to 1023 with f(n) = n. 1988 = 11111000011. So we also have all 32 numbers in the range 1023 to 2047 except for 11111111111 and 11111011111, giving another 30, or 92 in total.

It remains to prove the assertions above. f(n) odd follows by an easy induction. Next we show that if 2^m < 2n+1 < 2^m+1, then f(2n+1) = f(n) + 2^m. Again we use induction. It is true for m = 1 (f(3) = f(1) + 2). So suppose it is true for 1, 2, ... , m. Take 4n+1 so that 2^m+1 < 4n+1 < 2^m+2, then f(4n+1) = 2f(2n+1) - f(n) = 2(f(n) + 2^m) - f(n) = f(n) + 2^m+1 = f(2n) + 2^m+1, so it is true for 4n+1. Similarly, if 4n+3 satisfies, 2^m+1 < 4n+3 < 2^m+2, then f(4n+3) = 3f(2n+1) - 2f(n) = f(2n+1) + 2(f(n) + 2^m) - 2f(n) = f(2n+1) + 2^m+1, so it is true for 4n+3 and hence for m+1.

Finally, we prove the formula for f(2n+1). Let 2n+1 = b_r+1b_r...b₂b₁b₀ with b₀ = b_r+1 = 1. We use induction on r. So assume it is true for smaller values. Say b₁ = ... = b_s = 0 and b_s+1 = 1 (we may have s = 0, so that we have simply b₁ = 1). Then n = b_r+1 ... b₁ and f(n) = b_r+1b_s+2b_s+3...b_rb_s+1 by induction. So f(n) + 2^r+1 = b_r+10...0b_r+1b_s+2...b_rb_s+1, where there are s zeros. But we may write this as b_r+1b₁...b_sb_s+1...b_rb_r+1, since b₁ = ... = b_s = 0, and b_s+1 = b_r+1 = 1. But that is the formula for f(2n+1), so we have completed the induction. 

Problem B1

Show that the set of real numbers x which satisfy the inequality:

  1/(x - 1) + 2/(x - 2) + 3/(x - 3) + ... + 70/(x - 70) ≥ 5/4

is a union of disjoint intervals, the sum of whose lengths is 1988.

Solution

Let f(x) = 1/(x - 1) + 2/(x - 2) + 3/(x - 3) + ... + 70/(x - 70). For any integer n, n/(x - n) is strictly monotonically decreasing except at x = n, where it is discontinuous. Hence f(x) is strictly monotonically decreasing except at x = 1, 2, ... , 70. For n = any of 1, 2, ... , 70, n/(x - n) tends to plus infinity as x tends to n from above, whilst the other terms m/(x - m) remain bounded. Hence f(x) tends to plus infinity as x tends to n from above. Similarly, f(x) tends to minus infinity as x tends to n from below. Thus in each of the intervals (n, n+1) for n = 1, ... , 69, f(x) decreases monotonically from plus infinity to minus infinity and hence f(x) = 5/4 has a single foot x_n. Also f(x) ≥ 5/4 for x in (n, x_n] and f(x) < 5/4 for x in (x_n, n+1). If x < 0, then every term is negative and hence f(x) < 0 < 5/4. Finally, as x tends to infinity, every term tends to zero, so f(x) tends to zero. Hence f(x) decreases monotonically from plus infinity to zero over the range [70, infinity]. Hence f(x) = 5/4 has a single root x₇₀ in this range and f(x) >= 5/4 for x in (70, x₇₀] and f(x) < 5/4 for x > x₇₀. Thus we have established that f(x) ≥ 5/4 for x in any of the disjoint intervals (1, x₁], (2, x₂], ... , (70, x₇₀] and f(x) < 5/4 elsewhere.

The total length of these intervals is (x₁ - 1) + ... + (x₇₀ - 70) = (x₁ + ... + x₇₀) - (1 + ... + 70). The x_i are the roots of the 70th order polynomial obtained from 1/(x - 1) + 2/(x - 2) + 3/(x - 3) + ... + 70/(x - 70) = 5/4 by multiplying both sides by (x - 1) ... (x - 70). The sum of the roots is minus the coefficient of x⁶⁹ divided by the coefficient of x⁷⁰. The coefficient of x⁷⁰ is simply k, and the coefficient of x⁶⁹ is - (1 + 2 + ... + 70)k - (1 + ... + 70). Hence the sum of the roots is (1 + ... + 70)(1 + k)/k and the total length of the intervals is (1 + ... + 70)/k = 1/2 70·71 4/5 = 28·71 = 1988. 

Problem 5

ABC is a triangle, right-angled at A, and D is the foot of the altitude from A. The straight line joining the incenters of the triangles ABD and ACD intersects the sides AB, AC at K, L respectively. Show that the area of the triangle ABC is at least twice the area of the triangle AKL.

Solution

The key is to show that AK = AL = AD. We do this indirectly. Take K' on AB and L' on AC so that AK' = AL' = AD. Let the perpendicular to AB at K' meet the line AD at X. Then the triangles AK'X and ADB are congruent. Let J be the incenter of ADB and let r be the in-radius of ADB. Then J lies on the angle bisector of angle BAD a distance r from the line AD. Hence it is also the incenter of AK'X. Hence JK' bisects the right angle AK'X, so ∠AK'J = 45^o and so J lies on K'L'. An exactly similar argument shows that I, the incenter of ADC, also lies on K'L'. Hence we can identify K and K', and L and L'.

The area of AKL is AK·AL/2 = AD²/2, and the area of ABC is BC·AD/2, so we wish to show that 2AD ≤ BC. Let M be the midpoint of BC. Then AM is the hypoteneuse of AMD, so AM ≥ AD with equality if and only if D = M. Hence 2AD ≤ 2AM = BC with equality if and only if AB = AC. 

Problem B3

Let a and b be positive integers such that ab + 1 divides a² + b². Show that (a² + b²)/(ab + 1) is a perfect square.

Solution

A little experimentation reveals the following solutions: a, a³ giving a²; a³, a⁵ - a giving a²; and the recursive a₁ = 2, b₁ = 8, a_n+1 = b_n, b_n+1 = 4b_n - a_n giving 4. The latter may lead us to: if a² + b² = k(ab + 1), then take A = b, B = kb - a, and then A² + B² = k(AB + 1). Finally, we may notice that this can be used to go down as well as up.

So starting again suppose that a, b, k is a solution in positive integers to a² + b² = k(ab + 1). If a = b, then 2a² = k(a² + 1). So a² must divide k. But that implies that a = b = k = 1. Let us assume we do not have this trivial solution, so we may take a < b. We also show that a³ > b. For (b/a - 1/a)(ab + 1) = b² + b/a - b - 1/a < b² < a² + b². So k > b/a - 1/a. But if a³ < b, then b/a (ab + 1) > b² + a², so k < b/a. But now b > ak and < ak + 1, which is impossible. It follows that k ≥ b/a.

Now define A = ka - b, B = a. Then we can easily verify that A, B, k also satisfies a² + b² = k(ab + 1), and B and k are positive integers. Also a < b implies a² + b² < ab + b² < ab + b² + 1 + b/a = (ab + 1)(1 + b/a), and hence k < 1 + b/a, so ka - b < a. Finally, since k > b/a, ka - b ≥ 0. If ka - b > 0, then we have another smaller solution, in which case we can repeat the process. But we cannot have an infinite sequence of decreasing numbers all greater than zero, so we must eventually get A = ka - b = 0. But now A² + B² = k(AB + 1), so k = B². k was unchanged during the descent, so k is a perfect square.

A slightly neater variation on this is due to Stan Dolan

As above take a² + b² = k(ab + 1), so a, b, and k are all positive integers. Now fixing k take positive integers A, B such that A² + B² = k(AB + 1) (*) and min(A,B) is as small as possible. Assume B ≤ A. Regarding (*) as a quadratic for A, we see that the other root C satisfies A + C = kB, AC = B² - k. The second equation implies that C = B²/A - k/A < B. So C cannot be a positive integer (or the solution C, B would have min(C,B) < min(A,B)). But we have (A+1)(C+1) = A+C + AC + 1 = B² + (B-1)k + 1 > 0, so C > -1. C = kB - A is an integer, so C = 0. Hence k = B². 

Note that jumping straight to the minimal without the infinite descent avoids some of the verification needed in the infinite descent.

Read more

 

Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.