19th International Mathematical Olympiad 1977 Problems & Solutions

A1.  Construct equilateral triangles ABK, BCL, CDM, DAN on the inside of the square ABCD. Show that the midpoints of KL, LM, MN, NK and the midpoints of AK, BK, BL, CL, CM, DM, DN, AN form a regular dodecahedron.

A2.  In a finite sequence of real numbers the sum of any seven successive terms is negative, and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.

A3.  Given an integer n > 2, let V_n be the set of integers 1 + kn for k a positive integer. A number m in V_n is called indecomposable if it cannot be expressed as the product of two members of V_n. Prove that there is a number in V_n which can be expressed as the product of indecomposable members of V_n in more than one way (decompositions which differ solely in the order of factors are not regarded as different).

B1.  Define f(x) = 1 - a cos x - b sin x - A cos 2x - B sin 2x, where a, b, A, B are real constants. Suppose that f(x) ≥ 0 for all real x. Prove that a² + b² ≤ 2 and A² + B² ≤ 1.

B2.  Let a and b be positive integers. When a² + b² is divided by a + b, the quotient is q and the remainder is r. Find all pairs a, b such that q² + r = 1977.

B3.  The function f is defined on the set of positive integers and its values are positive integers. Given that f(n+1) > f(f(n)) for all n, prove that f(n) = n for all n. 

Solutions

Problem A1

Construct equilateral triangles ABK, BCL, CDM, DAN on the inside of the square ABCD. Show that the midpoints of KL, LM, MN, NK and the midpoints of AK, BK, BL, CL, CM, DM, DN, AN form a regular dodecahedron.

 

Solution

The most straightforward approach is to use coordinates. Take A, B, C, D to be (1,1), (-1,1), (-1,-1), (1,-1). Then K, L, M, N are (0, -2k), (2k, 0), (0, 2k), (-2k, 0), where k = (√3 - 1)/2. The midpoints of KL, LM, MN, NK are (k, -k), (k, k), (-k, k), (-k, -k). These are all a distance k√2 from the origin, at angles 315, 45, 135, 225 respectively. The midpoints of AK, BK, BL, CL, CM, DM, DN, AN are (h, j), (-h, j), (-j, h), (-j, -h), (-h, -j), (h, -j), (j, -h), (j, h), where h = 1/2, j = (1 - 1/2 √3). These are also at a distance k√2 from the origin, at angles 15, 165, 105, 255, 195, 345, 285, 75 respectively. For this we need to consider the right-angled triangle sides k, h, j. The angle x between h and k has sin x = j/k and cos x = h/k. So sin 2x = 2 sin x cos x = 2hj/k² = 1/2. Hence x = 15.

So the 12 points are all at the same distance from the origin and at angles 15 + 30n, for n = 0, 1, 2, ... , 11. Hence they form a regular dodecagon. 

Problem A2

In a finite sequence of real numbers the sum of any seven successive terms is negative, and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.

 

Solution

Answer: 16.

x₁ + ... + x₇ < 0, x₈ + ... + x₁₄ < 0, so x₁ + ... + x₁₄ < 0. But x₄ + ... + x₁₄ > 0, so x₁ + x₂ + x₃ < 0. Also x₅ + ... + x₁₁ < 0 and x₁ + ... + x₁₁ > 0, so x₄ > 0. If there are 17 or more elements then the same argument shows that x₅, x₆, x₇ > 0. But x₁ + ... + x₇ < 0, and x₅ + ... + x₁₁ < 0, whereas x₁ + ... + x₁₁ > 0, so x₅ + x₆ + x₇ < 0. Contradiction.

If we assume that there is a solution for n = 16 and that the sum of 7 consecutive terms is -1 and that the sum of 11 consecutive terms is 1, then we can easily solve the equations to get: 5, 5, -13, 5, 5, 5, -13, 5, 5, -13, 5, 5, 5, -13, 5, 5 and we can check that this works for 16. 

Problem A3

Given an integer n > 2, let V_n be the set of integers 1 + kn for k a positive integer. A number m in V_n is called indecomposable if it cannot be expressed as the product of two members of V_n. Prove that there is a number in V_n which can be expressed as the product of indecomposable members of V_n in more than one way (decompositions which differ solely in the order of factors are not regarded as different).

 

Solution

Take a, b, c, d = -1 (mod n). The idea is to take abcd which factorizes as ab.cd or ac.bd. The hope is that ab, cd, ac, bd will not factorize in V_n. But a little care is needed, since this is not necessarily true.

Try taking a = b = n - 1, c = d = 2n -1. a² must be indecomposable because it is less than the square of the smallest element in V_n. If ac = 2n² - 3n + 1 is decomposable, then we have kk'n + k + k' = 2n - 3 for some k, k' >= 1. But neither of k or k' can be 2 or more, because then the lhs is too big, and k = k' = 1 does not work unless n = 5. Similarly, if c² is decomposable, then we have kk'n + k + k' = 4n - 4. k = k' = 1 only works for n = 2, but we are told n > 2. k = 1, k' = 2 does not work (it would require n = 7/2). k = 1, k' = 3 only works for n = 8. Other possibilities make the lhs too big.

So if n is not 5 or 8, then we can take the number to be (n - 1)²(2n - 1)², which factors as (n - 1)² x (2n - 1)² or as (n - 1)(2n - 1) x (n - 1)(2n - 1). This does not work for 5 or 8: 16·81 = 36·36, but 36 decomposes as 6·6; 49·225 = 105·105, but 225 decomposes as 9·25.

For n = 5, we can use 3136 = 16·196 = 56·56. For n = 8, we can use 25921 = 49·529 = 161·161. 

Problem B1

Define f(x) = 1 - a cos x - b sin x - A cos 2x - B sin 2x, where a, b, A, B are real constants. Suppose that f(x) ≥ 0 for all real x. Prove that a² + b² ≤ 2 and A² + B² ≤ 1.

 

Solution

Take y so that cos y = a/√(a² + b²), sin y = b/√(a² + b²), and z so that cos 2z = A/√(A² + B²), sin 2z = B/√(A² + B²). Then f(x) = 1 - c cos(x - y) - C cos2(x - z), where c = √(a² + b²), C = √(A² + B²).

f(z) + f(π + z) ≥ 0 gives C ≤ 1. f(y + π/4) + f(y - π/4) ≥ 0 gives c ≤ √2. 

Problem B2

Let a and b be positive integers. When a² + b² is divided by a + b, the quotient is q and the remainder is r. Find all pairs a, b such that q² + r = 1977.

 

Solution

a² + b² >= (a + b)²/2, so q ≥ (a + b)/2. Hence r < 2q. The largest square less than 1977 is 1936 = 44². 1977 = 44² + 41. The next largest gives 1977 = 43² + 128. But 128 > 2.43. So we must have q = 44, r = 41. Hence a² + b² = 44(a + b) + 41, so (a - 22)² + (b - 22)² = 1009. By trial, we find that the only squares with sum 1009 are 28² and 15². This gives two solutions 50, 37 or 50, 7. 

Problem B3

The function f is defined on the set of positive integers and its values are positive integers. Given that f(n+1) > f(f(n)) for all n, prove that f(n) = n for all n.

 

Solution

The first step is to show that f(1) < f(2) < f(3) < ... . We do this by induction on n. We take S_n to be the statement that f(n) is the unique smallest element of { f(n), f(n+1), f(n+2), ... }.

For m > 1, f(m) > f(s) where s = f(m-1), so f(m) is not the smallest member of the set {f(1), f(2), f(3), ... }. But the set is bounded below by zero, so it must have a smallest member. Hence the unique smallest member is f(1). So S₁ is true.

Suppose S_n is true. Take m > n+1. Then m-1 > n, so by S_n, f(m-1) > f(n). But S_n also tells us that f(n) > f(n-1) > ... > f(1), so f(n) ≥ n - 1 + f(1) ≥ n. Hence f(m-1) ≥ n+1. So f(m-1) belongs to { n+1, n+2, n+3, .. }. But we are given that f(m) > f(f(m-1)), so f(m) is not the smallest element of { f(n+1), f(n+2), f(n+3), ... }. But there must be a smallest element, so f(n+1) must be the unique smallest member, which establishes S_n+1. So, S_n is true for all n.

So n ≤ m implies f(n) <= f(m). Suppose for some m, f(m) ≥ m+1, then f(f(m)) ≥ f(m+1). Contradiction. Hence f(m) ≤ m for all m. But since f(1) ≥1 and f(m) > f(m-1) > ... > f(1), we also have f(m) ≥ m. Hence f(m) = m for all m.

 

Solutions are also available in:   Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.