22nd International Mathematical Olympiad 1981 Problems & Solutions

A1.  P is a point inside the triangle ABC. D, E, F are the feet of the perpendiculars from P to the lines BC, CA, AB respectively. Find all P which minimise:         BC/PD + CA/PE + AB/PF.

A2.  Take r such that 1 ≤ r ≤ n, and consider all subsets of r elements of the set {1, 2, ... , n}. Each subset has a smallest element. Let F(n,r) be the arithmetic mean of these smallest elements. Prove that:         F(n,r) = (n+1)/(r+1).

A3.  Determine the maximum value of m² + n², where m and n are integers in the range 1, 2, ... , 1981 satisfying (n² - mn - m²)² = 1.

B1. (a)  For which n > 2 is there a set of n consecutive positive integers such that the largest number in the set is a divisor of the least common multiple of the remaining n - 1 numbers? (b)  For which n > 2 is there exactly one set having this property?

B2.  Three circles of equal radius have a common point O and lie inside a given triangle. Each circle touches a pair of sides of the triangle. Prove that the incenter and the circumcenter of the triangle are collinear with the point O.

B3.  The function f(x,y) satisfies: f(0,y) = y + 1, f(x+1,0) = f(x,1), f(x+1,y+1) = f(x,f(x+1,y)) for all non-negative integers x, y. Find f(4, 1981). 

Solutions

Problem A1

P is a point inside the triangle ABC. D, E, F are the feet of the perpendiculars from P to the lines BC, CA, AB respectively. Find all P which minimise:

        BC/PD + CA/PE + AB/PF.

 

Solution

We have PD.BC + PE.CA + PF.AB = 2 area of triangle. Now use Cauchy's inequality with x₁ = √(PD·BC), x₂ = √(PE·CA), x₃ = √(PF·AB), and y₁ = √(BC/PD), y₂ = √(CA/PE), y₃ = √(AB/PF). We get that (BC + CA + AB)² < 2 x area of triangle x (BC/PD + CA/PE + AB/PF) with equality only if x_i/y_i = const, ie PD = PE = PF. So the unique minimum position for P is the incenter. 

Problem A2

Take r such that 1 ≤ r ≤ n, and consider all subsets of r elements of the set {1, 2, ... , n}. Each subset has a smallest element. Let F(n,r) be the arithmetic mean of these smallest elements. Prove that:

        F(n,r) = (n+1)/(r+1).

 

Solution

Denote the binomial coefficient n!/(r!(n-r)!) by nCr.

Evidently nCr F(n,r) = 1 (n-1)C(r-1) + 2 (n-2)C(r-1) + ... + (n-r+1) (r-1)C(r-1). [The first term denotes the contribution from subsets with smallest element 1, the second term smallest element 2 and so on.]

Let the rhs be g(n,r). Then, using the relation (n-i)C(r-1) - (n-i-1)C(r-2) = (n-i-1)C(r-1), we find that g(n,r) - g(n-1,r-1) = g(n-1,r), and we can extend this relation to r=1 by taking g(n,0) = n+1 = (n+1)C1. But g(n,1) = 1 + 2 + ... + n = n(n+1)/2 = (n+1)C2. So it now follows by an easy induction that g(n,r) = (n+1)C(r+1) = nCr (n+1)/(r+1). Hence F(n,r) = (n+1)/(r+1).

A more elegant solution by Oliver Nash is as follows

Let k be the smallest element. We want to evaluate g(n, r) = ∑_{k=1 to n-r+1} k   (n-k)C(r-1). Consider the subsets with r+1 elements taken from 1, 2, 3, ... , n+1. Suppose k+1 is the second smallest element. Then there are k   (n-k)C(r-1) possible subsets. So g(n, r) = (n+1)C(r+1). Hence F(n, r) = (n+1)C(r+1) / nCr = (n+1)/(r+1), as required. 

Problem A3

Determine the maximum value of m² + n², where m and n are integers in the range 1, 2, ... , 1981 satisfying (n² - mn - m²)² = 1.

 

Solution

Experimenting with small values suggests that the solutions of n² - mn - m² = 1 or -1 are successive Fibonacci numbers. So suppose n > m is a solution. This suggests trying m+n, n: (m+n)² - (m+n)n - n² = m² + mn - n² = -(n² - mn - m²) = 1 or -1. So if n > m is a solution, then m+n, n is another solution. Running this forward from 2,1 gives 3,2; 5,3; 8,5; 13,8; 21,13; 34,21; 55,34; 89,55; 144,89; 233,144; 377,233; 610,377; 987,610; 1597,987; 2584,1597.

But how do we know that there are no other solutions? The trick is to run the recurrence the other way. For suppose n > m is a solution, then try m, n-m: m² - m(n-m) - (n-m)² = m² + mn - n² = -(n² - mn - m²) = 1 or -1, so that also satisfies the equation. Also if m > 1, then m > n-m (for if not, then n >= 2m, so n(n - m) >= 2m², so n² - nm - m² >= m² > 1). So given a solution n > m with m > 1, we have a smaller solution m > n-m. This process must eventually terminate, so it must finish at a solution n, 1 with n > 1. But the only such solution is 2, 1. Hence the starting solution must have been in the forward sequence from 2, 1.

Hence the solution to the problem stated is 1597² + 987². 

Problem B1

(a)  For which n > 2 is there a set of n consecutive positive integers such that the largest number in the set is a divisor of the least common multiple of the remaining n - 1 numbers?

(b)  For which n > 2 is there exactly one set having this property?

 

Solution

(a)  n = 3 is not possible. For suppose x was the largest number in the set. Then x cannot be divisible by 3 or any larger prime, so it must be a power of 2. But it cannot be a power of 2, because 2^m - 1 is odd and 2^m - 2 is not a positive integer divisible by 2^m.

For k ≥ 2, the set 2k-1, 2k , ... , 4k-2 gives n = 2k. For k ≥ 3, so does the set 2k-5, 2k-4, ... , 4k-6. For k ≥ 2, the set 2k-2, 2k-3, ... , 4k-2 gives n = 2k+1. For k ≥ 4 so does the set 2k-6,2k-5, ... , 4k-6. So we have at least one set for every n ≥ 4, which answers (a).

(b)  We also have at least two sets for every n ≥ 4 except possibly n = 4, 5, 7. For 5 we may take as a second set: 8, 9, 10, 11, 12, and for 7 we may take 6, 7, 8, 9 ,10, 11, 12. That leaves n = 4. Suppose x is the largest number in a set with n =4. x cannot be divisible by 5 or any larger prime, because x-1, x-2, x-3 will not be. Moreover, x cannot be divisible by 4, because then x-1 and x-3 will be odd, and x-2 only divisible by 2 (not 4). Similarly, it cannot be divisible by 9. So the only possibilities are 1, 2, 3, 6. But we also require x ≥ 4, which eliminates the first three. So the only solution for n = 4 is the one we have already found: 3, 4, 5, 6. 

Problem B2

Three circles of equal radius have a common point O and lie inside a given triangle. Each circle touches a pair of sides of the triangle. Prove that the incenter and the circumcenter of the triangle are collinear with the point O.

 

Solution

Let the triangle be ABC. Let the center of the circle touching AB and AC be D, the center of the circle touching AB and BC be E, and the center of the circle touching AC and BC be F. Because the circles center D and E have the same radius the perpendiculars from D and E to AB have the same length, so DE is parallel to AB. Similarly EF is parallel to BC and FD is parallel to CA. Hence DEF is similar and similarly oriented to ABC. Moreover D must lie on the angle bisector of A since the circle center D touches AB and AC. Similarly E lies on the angle bisector of B and F lies on the angle bisector of C. Hence the incenter I of ABC is also the incenter of DEF and acts as a center of symmetry so that corresponding points P of ABC and P' of DEF lie on a line through I with PI/P'I having a fixed ratio. But OD = OE = OF since the three circles have equal radii, so O is the circumcenter of DEF. Hence it lies on a line with I and the circumcenter of ABC. 

Problem B3

The function f(x,y) satisfies: f(0,y) = y + 1, f(x+1,0) = f(x,1), f(x+1,y+1) = f(x,f(x+1,y)) for all non-negative integers x, y. Find f(4, 1981).

 

Solution

f(1,n) = f(0,f(1,n-1)) = 1 + f(1,n-1). So f(1,n) = n + f(1,0) = n + f(0,1) = n + 2.

f(2,n) = f(1,f(2,n-1)) = f(2,n-1) + 2. So f(2,n) = 2n + f(2,0) = 2n + f(1,1) = 2n + 3.

f(3,n) = f(2,f(3,n-1)) = 2f(3,n-1) + 3. Let u_n = f(3,n) + 3, then u_n = 2u_n-1. Also u₀ = f(3,0) + 3 = f(2,1) + 3 = 8. So u_n = 2ⁿ⁺³, and f(3,n) = 2ⁿ⁺³ - 3.

f(4,n) = f(3,f(4,n-1)) = 2^f(4,n-1)+3 - 3. f(4,0) = f(3,1) = 2⁴ - 3 = 13. We calculate two more terms to see the pattern: f(4,1) = 2²⁴ - 3, f(4,2) = 2²²⁴ - 3. In fact it looks neater if we replace 4 by 2², so that f(4,n) is a tower of n+3 2s less 3.

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.