Math Olympiad
Math Activities   User Guide   Help   Kids Math Books   Questions & Answers
Search Math Resources - It's easy!
Math Olympiad
Math Olympiad
Math Olympiad
more:  Math Books|Math Activities 
  Home page Home      FAQ FAQs      Sitemap Site map      Advanced Search Search      Contact Contact      Copyright Copyright      Buy Math CD Buy Math CD
IMO Problems & Solutions

International Mathematical Olympiad Problems

 

19th International Mathematical Olympiad 1977 Problems
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 Vn be the set of integers 1 + kn for k a positive integer. A number m in Vn is called indecomposable if it cannot be expressed as the product of two members of Vn. Prove that there is a number in Vn which can be expressed as the product of indecomposable members of Vn 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 a2 + b2 ≤ 2 and A2 + B2 ≤ 1.
B2.  Let a and b be positive integers. When a2 + b2 is divided by a + b, the quotient is q and the remainder is r. Find all pairs a, b such that q2 + 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.

 




Solution

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/k2 = 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.

x1 + ... + x7 < 0, x8 + ... + x14 < 0, so x1 + ... + x14 < 0. But x4 + ... + x14 > 0, so x1 + x2 + x3 < 0. Also x5 + ... + x11 < 0 and x1 + ... + x11 > 0, so x4 > 0. If there are 17 or more elements then the same argument shows that x5, x6, x7 > 0. But x1 + ... + x7 < 0, and x5 + ... + x11 < 0, whereas x1 + ... + x11 > 0, so x5 + x6 + x7 < 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 Vn be the set of integers 1 + kn for k a positive integer. A number m in Vn is called indecomposable if it cannot be expressed as the product of two members of Vn. Prove that there is a number in Vn which can be expressed as the product of indecomposable members of Vn 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 Vn. But a little care is needed, since this is not necessarily true.

Try taking a = b = n - 1, c = d = 2n -1. a2 must be indecomposable because it is less than the square of the smallest element in Vn. If ac = 2n2 - 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 c2 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)2(2n - 1)2, which factors as (n - 1)2 x (2n - 1)2 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 a2 + b2 ≤ 2 and A2 + B2 ≤ 1.

 

Solution

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

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 a2 + b2 is divided by a + b, the quotient is q and the remainder is r. Find all pairs a, b such that q2 + r = 1977.

 

Solution

a2 + b2 >= (a + b)2/2, so q ≥ (a + b)/2. Hence r < 2q. The largest square less than 1977 is 1936 = 442. 1977 = 442 + 41. The next largest gives 1977 = 432 + 128. But 128 > 2.43. So we must have q = 44, r = 41. Hence a2 + b2 = 44(a + b) + 41, so (a - 22)2 + (b - 22)2 = 1009. By trial, we find that the only squares with sum 1009 are 282 and 152. 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 Sn 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 S1 is true.

Suppose Sn is true. Take m > n+1. Then m-1 > n, so by Sn, f(m-1) > f(n). But Sn 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 Sn+1. So, Sn 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.

Division Lessons
<<  Double division Dividing Fractions >>
Related subject
Common keywords: APMO, Chinese, Iberoamerican, Polish.

Mathematical Olympiad Problems & Solutions
Terms & Conditions | Legal notices | About | Sitemap | Copyright | Contact | Help
Copyright 2009 - Math Olympiad. All Rights Reserved. No portion of the content may be directly or indirectly copied, published, reproduced, modified, performed, displayed, sold, translated, transmitted, broadcast, rewritten for broadcast or publication or redistributed in any medium. Nor may any portion of the content be stored in a computer or distributed over any network.
All trademarks, service marks and logos used in this site are the trademarks, service marks or logos of their respective owners.