30th International Mathematical Olympiad 1989 Problems & Solutions

A1. Prove that the set {1, 2, ... , 1989} can be expressed as the disjoint union of subsets A₁, A₂, ... , A₁₁₇ in such a way that each A_i contains 17 elements and the sum of the elements in each A_i is the same.

A2. In an acute-angled triangle ABC, the internal bisector of angle A meets the circumcircle again at A₁. Points B₁ and C₁ are defined similarly. Let A₀ be the point of intersection of the line AA₁ with the external bisectors of angles B and C. Points B₀ and C₀ are defined similarly. Prove that the area of the triangle A₀B₀C₀ is twice the area of the hexagon AC₁BA₁CB₁ and at least four times the area of the triangle ABC.

A3. Let n and k be positive integers, and let S be a set of n points in the plane such that no three points of S are collinear, and for any point P of S there are at least k points of S equidistant from P. Prove that k < 1/2 + √(2n).

B1. Let ABCD be a convex quadrilateral such that the sides AB, AD, BC satisfy AB = AD + BC. There exists a point P inside the quadrilateral at a distance h from the line CD such that AP = h + AD and BP = h + BC. Show that: 1/√h ≥ 1/√AD + 1/√BC.

B2. Prove that for each positive integer n there exist n consecutive positive integers none of which is a prime or a prime power.

B3. A permutation {x₁, x₂, ... , x_m} of the set {1, 2, ... , 2n} where n is a positive integer is said to have property P if |x_i - x_i+1| = n for at least one i in {1, 2, ... , 2n-1}. Show that for each n there are more permutations with property P than without.

Solutions

Problem A1

Prove that the set {1, 2, ... , 1989} can be expressed as the disjoint union of subsets A₁, A₂, ... , A₁₁₇ in such a way that each A_i contains 17 elements and the sum of the elements in each A_i is the same.

Solution

We construct 116 sets of three numbers. Each set sums to 3 x 995 = 2985. The 348 numbers involved form 174 pairs {r, 1990 - r}. At this point we are essentially done. We take a 117th set which has one {r, 1990 - r} pair and 995. The original 1989 numbers comprise 995 and 994 {r, 1990 - r} pairs. We have used up 995 and 175 pairs, leaving just 819 pairs. We now add 7 pairs to each of our 117 sets, bringing the total of each set up to 2985 + 7.1990 = 1990 x 17/2.

It remains to exhibit the 116 sets. There are many possibilities. We start with:
301, 801, 1883 and the "complementary" set 1990 - 301 = 1689, 1990 - 801 = 1189, 1990 - 1883 = 107. We then add one to each of the first two numbers to get:
302, 802, 1881 and 1688, 1188, 109, and so on:
303, 803, 1879 and 1687, 1187, 111,
...
358, 858, 1769 and 1632, 1132, 221.
We can immediately see that these triples are all disjoint. So the construction is complete.

Problem A2

In an acute-angled triangle ABC, the internal bisector of angle A meets the circumcircle again at A₁. Points B₁ and C₁ are defined similarly. Let A₀ be the point of intersection of the line AA₁ with the external bisectors of angles B and C. Points B₀ and C₀ are defined similarly. Prove that the area of the triangle A₀B₀C₀ is twice the area of the hexagon AC₁BA₁CB₁ and at least four times the area of the triangle ABC.

Solution

By Marcin Mazur, University of Illinois at Urbana-Champaign

Let I be the point of intersection of AA₀, BB₀, CC₀ (the in-center). BIC = 180 - 1/2 ABC - 1/2 BCA = 180 - 1/2 (180 - CAB) = 90 + 1/2 CAB. Hence CA₁B = 180 - CAB [BA₁CA is cyclic] = 2(180 - BIC) = 2CA₀B. But A₁B = A₁C, so A₁ is the center of the circumcircle of BCA₀. But I lies on this circumcircle (IBA₀ = ICA₀ = 90), and hence A₁A₀ = A₁I.

Hence area IBA₁ = area A₀BA₁ and area ICA₁ = area A₀CA₁. Hence area IBA₀C = 2 area IBA₁C. Similarly, area ICB₀A = 2 area ICB₁A and area IAC₀B = 2 area IAC₁B. Hence area A₀B₀C₀ = 2 area hexagon AB₁CA₁BC₁.

A neat solution for the rest is as follows by Thomas Jäger

Let H be the orthocentre of ABC. Let H₁ be the reflection of H in BC, so H₁ lies on the circumcircle. So area BCH = area BCH₁ <= area BCA₁. Adding to the two similar inequalities gives area ABC <= area hexagon - area ABC.

Mazur's solution was as follows

CAB = 180^o - CA₁B and A₁B = A₁C, so A₁BC = 90^o - 1/2 CA₁B = 1/2 CAB. Hence the perpendicular from A₁ to BC has length 1/2 BC tan(CAB/2) and area CA₁B = 1/4 BC² tan(CAB/2).

Put r = radius of in-circle of ABC, x = cot(CAB/2), y = cot(ABC/2), z = cot(BCA/2). Then BC = r(y + z) and area CA₁B = r²(y + z)²/(4x). Also area BIC = 1/2 r BC. Similarly for the other triangles, so area ABC = area BIC + area CIA + area AIB = r²(x + y + z). We have to show that area ABC ≤ area CA₁B + area AB₁C + area BC₁A, or (x + y + z) ≤ (y + z)²/(4x) + (z + x)²/(4y) + (x + y)²/(4z).

Putting s = x + y + z, this is equivalent to: 4s ≤ (s - x)²/x + (s - y)²/y + (s - z)²/z, or 9s ≤ s²(1/x + 1/y + 1/z), but this is just the statement that the arithmetic mean of x, y, z is not less than the harmonic mean.

Note in passing that the requirement for ABC to be acute is unnecessary.

Problem A3

Let n and k be positive integers, and let S be a set of n points in the plane such that no three points of S are collinear, and for any point P of S there are at least k points of S equidistant from P. Prove that k < 1/2 + √(2n).

Solution

Three variants on a theme, all kindly supplied by others (I spent 2 hours failing to solve it). My favorite first.

By Eli Bachmutsky

Consider the pairs P, {A, B}, where P, A, B are points of S, and P lies on the perpendicular bisector of AB. There are at least n k(k - 1)/2 such pairs, because for each point P, there are at least k points equidistant from P and hence at least k(k - 1)/2 pairs of points equidistant from P.

If k ≥ 1/2 + √(2n), then k(k - 1) ≥ 2n - 1/4 > 2(n - 1), and so there are more than n(n - 1) pairs P, {A, B}. But there are only n(n - 1)/2 possible pairs {A, B}, so for some {A₀, B₀} we must be able to find at least 3 points P on the perpendicular bisector of A₀B₀. But these points are collinear, contradicting the assumption in the question.

From an anonymous source

Let the points be P₁, P₂, ... , P_n. Let C_i be a circle center P_i containing at least k points of S. There are at least nk pairs (C_i,P_j), where P_j lies on C_i. Hence there must a point P lying on at least k circles. Take k such circles C_α. For each such circle C_α, take a subset S_α comprising exactly k points of S ∩ C_α.

We now count the points in ∪ S_α. Apart from P, there are k-1 points in each S_α. So we start with 1 + k(k-1). But this counts some points more than once. Each pair (S_α, S_β) (with α ≠ β) has at most one common point apart from P (because distinct circles have at most two common points). So we deduct 1 for each of the 1/2 k(k - 1) pairs (S_α, S_β), giving 1 + k(k - 1) - 1/2 k(k - 1) (*).

If Q (≠ P) is in exactly r sets S_α, then it is counted r times in the second term k(k - 1), and subtracted 1/2 r(r - 1) times in the third term. So it is counted 1/2 r(3 - r) times in all. That is correct for r = 0, 1 or 2 and too low for r > 2. So (*) is ≤ |∪ S_α|. Clearly |∪ S_α| ≤ n, so n ≥ 1 + k(k - 1)/2 = (k - 1/2)²/2 + 7/8 > (k - 1/2)²/2. Hence √(2n) + 1/2 > k.

By Thomas Jäger

Define P_i and S_i as above. Let g(i) be the number of S_a containing P_i, and let f(i, j) be |S_i ∩ S_j|. Let h(x) = x(x - 1)/2. We count the number N of pairs i, {a, b}, where point i is in S_a and S_b.

Point i is in g(i) sets S_j, from which we can choose S_a,S_b in h(g(i)) ways. Hence N = ∑ h(g(i)). But f(a, b) points are in S_a and S_b, so N = ∑ f(a, b). But, since distinct circles intersect in at most 2 points, f(a, b) ≤ 2, so ∑ f(a, b) ≤ h(n) 2. We conclude that 2 h(n) ≥ ∑ h(g(i)).

h is a convex function, so 1/n ∑ h(g(i)) ≥ h(1/n ∑ g(i)) = n h(1/n nk) = n h(k). Hence n - 1 ≥ h(k), which gives the result, as above.

Problem B1

Let ABCD be a convex quadrilateral such that the sides AB, AD, BC satisfy AB = AD + BC. There exists a point P inside the quadrilateral at a distance h from the line CD such that AP = h + AD and BP = h + BC. Show that:

1/√h ≥ 1/√AD + 1/√BC.

Solution

by Gerhard Wöginger, Technical University, Graz

Let C_A be the circle center A, radius AD, and C_B the circle center B, radius BC. The circles touch on AB. Let C_P the the circle center P, radius h. C_P touches C_A and C_B and CD. Let t be the common tangent to C_A and C_B whose two points of contact are on the same side of AB as C and D. Then C_P is confined inside the curvilinear triangle whose sides are segments of t, C_A and C_B. Evidently h attains its maximum value, for given lengths AB, AD, BC, when C_P touches t, in which case D must be the point at which t touches C_A, and C the point at which it touches C_B. Suppose E is the point at which t touches C_P.

Angles ADC and BCD are right angles, so CD² = AB² - (AD - BC)² = 4 AD BC. Similarly, DE² = 4 h AD, and CE² = 4 h BC. But CD = DE + CE, so 1/√h = 1/√AD + 1/√BC. This gives the maximum value of h, so in general we have the inequality stated.

Problem B2

Prove that for each positive integer n there exist n consecutive positive integers none of which is a prime or a prime power.

Solution

Consider (N!)²+2, (N!)²+3, ... , (N!)²+N. (N!)²+r is divisible by r, but ((N!)²+r)/r = N! (N!/r) + 1, which is greater than one, but relatively prime to r since N! (N!/r) is divisible by r. For each r we may take a prime p_r dividing r, so (N!)²+r is divisible by p_r, but is not a power of p_r. Hence it is not a prime or a prime power. Taking N = n+1 gives n consecutive numbers as required.

Problem B3

A permutation {x₁, x₂, ... , x_m} of the set {1, 2, ... , 2n} where n is a positive integer is said to have property P if |x_i - x_i+1| = n for at least one i in {1, 2, ... , 2n-1}. Show that for each n there are more permutations with property P than without.

Solution

from Arthur Engel, Problem-Solving Strategies, Springer 1998 [Problem books in mathematics series], ISBN 0387982191. A rather good training book.

Let A_k be the set of permutations with k and k+n in neighboring positions, and let A be the set of permutations with property P, so that A is the union of the A_k.

But |A_k| = 2 (2n - 1)! (two orders for k, k+n and then (2n - 1)! ways of arranging the 2n - 1 items, treating k, k+n as a single item). Similarly, |A_k∩A_l| = 4 (2n - 2)! So |A| ≥ (2n - 2)! [n.2(2n -1) - n(n - 1)/2 4] = 2n² (2n - 2)! > (2n)!/2.

Read more