31st IMO 1990 shortlisted Problems and Solutions

1.  Is there a positive integer which can be written as the sum of 1990 consecutive positive integers and which can be written as a sum of two or more consecutive positive integers in just 1990 ways?

2.  11 countries each have 3 representatives. Is it possible to find 1990 committees C₁, C₂, ... , C₁₉₉₀ such that each committee has just one representative from each country, no two committees have the same members, and every two committees have at least one member in common except for the pairs (C₁, C₂), (C₂, C₃), (C₃, C₄), ... , (C₁₉₉₁, C₁₉₉₂), (C₁₉₉₂, C₁)?

4.  The set of all positive integers is divided into r disjoint subsets. Show that for one of them we can find a positive integer m such that for any k there are numbers a₁ < a₂ < ... < a_k in the subset with the difference between consecutive numbers in the sequence at most m.

5.  The triangle ABC has unequal sides, centroid G, incenter I and orthocenter H. Show that angle GIH > 90^o.

7.  Define f(0) = 0, f(1) = 0, and f(n+2) = 4ⁿ⁺²f(n+1) - 16ⁿ⁺¹f(n) + n 2^sq(n), were sq(n) = n². Show that f(1989), f(1990) and f(1991) are all divisible by 13.

8.  For a positive integer k, let f₁(k) be the square of the sum of its digits. Let f_n+1(k) = f₁( f_n(k) ). Find the value of f₁₉₉₁(2¹⁹⁹⁰).

9.  ABC is a triangle with incenter I. M is the midpoint of AC and N is the midpoint of AB. The lines NI and AC meet at X, and the lines MI and AB meet at Y. The triangles AXY and ABC have the same area. Find angle A.

10.  A plane cuts a right circular cone of volume V into two parts. The plane is tangent to the circumference of 

the base of the cone and passes through the midpoint of the altitude. Find the volume of the smaller part.

12.  ABC is a triangle with angle bisectors AD and BF. The lines AD, BF meet the line through C parallel to AB at E and G respectively, and FG = DE. Show that CA = CB.

13.  A gymnast ascends a ladder of n steps A steps at a time and descends B steps at a time. Find the smallest n such that starting from the bottom, he can get to the top and back again. Note that he does not have to go directly to the top. For example, if A = 3, B = 2, then n = 4 works: 0 3 1 4 2 0.

14.  R is the rectangle with vertices (0, 0), (m, 0), (0, n), (m, n), where m and n are odd integers. R is divided into triangles. Each triangle has at least one good side which lies on a line of the form x = i or y = j, where i and j are integers, and has the altitude to this side of length 1. Any side which is not a good side is a common side to two triangles. Show that there are at least two triangles each with two good sides.

15.  For which k can the set {1990, 1991, 1992, ... , 1990 + k} be divided into two disjoint subsets with equal sums?

17.  Holes are drilled through a long diagonal of each of pqr unit cubes and the cubes are threaded are put onto a string. For which p, q, r can the cubes be arranged to form a p x q x r cube (whilst still on the string and with neighbouring cubes on the string continuing to touch at their adjacent vertices)? Suppose that the ends of the string are tied to form a loop so that every cube touches two neighbouring cubes. For which p, q, r can a cube be made now?

18.  a <= b are positive integers, m = (a + b)/2. Define the function f on the integers by f(n) = n + a if n < m, n - b if n >= m. Let f₁(n) = f(n), f₂(n) = f( f₁(n) ), f₃(n) = f( f₂(n) ) etc. Find the smallest k such that f_k(0) = 0.

19.  P is a point inside a regular tetrahedron of unit volume. The four planes through P parallel to the faces of the tetrahedron partition it into 14 pieces. Let v(P) be the total volume of the pieces which are neither a tetrahedron nor a parallelepiped (in other words, the pieces which are adjacent to an edge, but not to a vertex). Find the smallest and largest possible values for v(P).

20.  Show that every positive integer n > 1 has a positive multiple less than n⁴ which uses at most 4 different digits.

21.  Ten cities are served by two airlines. All services are both ways. There is a direct service between any two cities. Show that at least one of the airlines can offer two disjoint round trips, each with an odd number of landings.

23.  w, x, y, z are non-negative reals such that wx + xy + yz + zw = 1. Show that w³/(x + y + z) + x³/(w + y + z) + y³/(w + x + z) + z³/(w + x + y) >= 1/3.

25.  Let p(x) be a cubic polynomial with rational coefficients. q₁, q₂, q₃, ... is a sequence of rationals such that q_n = p(q_n+1) for all positive n. Show that for some k, we have q_n+k = q_n for all positive n.

26.  Find all positive integers n such that every positive integer with n digits, one of which is 7 and the others 1, is prime.

27.  Show that it is not possible to find a finite number of points P₁, P₂, ... , P_n in the plane such that each point has rational coordinates, each edge P₁P₂, P₂P₃, P₃P₄, ... , P_n-1P_n, P_nP₁ has length 1, and n is odd.

Note: problems 3, 6, 11, 16, 22 and 24 were used in the Olympiad and are not shown here.

Solutions

Problem 9

ABC is a triangle with incenter I. M is the midpoint of AC and N is the midpoint of AB. The lines NI and AC meet at X, and the lines MI and AB meet at Y. The triangles AXY and ABC have the same area. Find angle A.

 

Solution

Solution by Vivek Kumar Mehra

Answer: A = 60^o.

By similar triangles, h/r = 1 + z/k. But AI bisects angle NAX, so z/k = c/(2x). Hence h = r(1 + c/(2x) ). Similarly, if h' is the length of the perpendicular from M to AB, we have h' = r(1 + b/(2y) ). Hence (h/r - 1)(h'/r - 1) = 1/4 (*)

We are given that xy = bc. Also r = (2 area ABC)/(a + b + c) = (bc sin A)/(a + b + c) But 2h = c sin A, and 2h' = b sin A. So substituting in (*) and simplifying we get a² = b² + c² - bc. Comparing with the cosine formula, we get A = 60^o. 

Problem 20

Show that every positive integer n > 1 has a positive multiple less than n⁴ which uses at most 4 different digits.

 

Solution

Solution by Demetres Christofides

Take m such that 2^m-1 ≤ n < 2^m. There are 2^m > n numbers with m digits or less and whose digits are all 0 or 1, so (pigeonhole principle) two of them must be equal mod n. So their difference is divisible by n and ≤ 10^m/9 = 16^m-1(10/16)^m-1(10/9), which is < 16^m-1 ≤ n⁴ for m > 1. But the difference between any two numbers with digits 0 and 1 only has the digits 0, 1, 8 and 9. 

Problem 23

w, x, y, z are non-negative reals such that wx + xy + yz + zw = 1. Show that w³/(x + y + z) + x³/(w + y + z) + y³/(w + x + z) + z³/(w + x + y) ≥ 1/3.

 

Solution

Solution by Demetres Christofides

Put s = w + x + y + z. Put A = w³/(s-w) + x³/(s-x) + y³/(s-y) + z³/(s-z), B = w² + x² + y² + z², C = w(s-w) + x(s-x) + y(s-y) + z(s-z) = 2 + 2wy + 2xz. By Cauchy-Schwartz, we have AC >= B².

We have (w-x)² + (x-y)² + (y-z)² + (z-w)² ≥ 0, so B ≥ (wx + xy + yz + zw) = 1. Also (w - y)² + (x - z)² ≥ 0, so B ≥ 2wy + 2xz. So if 2wy + 2xz ≤ 1, then A ≥ 1/C ≥ 1/3. If 2wy + 2xz > 1, then C > 3, so (C-2)/C > 1 - 2/C > 1/3. Hence AC ≥ B² ≥ B ≥ (C-2), so A > 1/3.

Problem 26

Find all positive integers n such that every positive integer with n digits, one of which is 7 and the others 1, is prime.

 

Solution

Answer: n = 1, 2.

Solution by Demetres Christofides

For n = 1, we note that 7 is prime. For n = 2, we note that 17 and 71 are prime. So the result is true for n = 1, 2.

Note that 111111 = 111.1001 is divisible by 7 and 13. Now 7111 is divisible by 13, so 7111, 7111111111, 7111111111111111, ... are all divisible by 13. In other words the result is not true for n = 4 mod 6. Similarly, since 7 divides 11711 it is not true for n = 5 mod 6. Also since 7 divides 7, it also divides 7111111 etc, so the result is not true for n = 1 mod 6 and n > 1. Also 611 is divisible by 13 and hence 11111711 is divisible by 13, so the result is not true for n = 2 mod 6 and n > 2. Finally, if n = 0 or 3 mod 6, then any number with n digits all 1 or 7, is divisible by 3 and hence not prime.

Read more »

Posted in: IMO shortlist

30th IMO 1989 shortlisted Problems and Solutions

1.  Ali Baba has a rectangular piece of carpet. He finds that if he lays if flat on the floor of either of his storerooms then each corner of the carpet touches a different wall of the room. He knows that the storerooms have widths 38 and 50 feet and the same (unknown but integral) length. What are the dimensions of the carpet?

2.  Prove that for n > 1 the polynomial xⁿ/n! + x^n-1/(n-1)! + ... + x/1! + 1 has no rational roots.

3.  The polynomial xⁿ + n x^n-1 + a₂x^n-2 + ... + a₀ has n roots whose 16th powers have sum n. Find the roots.

4.  The angle bisectors of the triangle ABC meet the circumcircle again at A'B'C'. Show that 16 (area A'B'C')³ ≥ 27 area ABC R⁴, where R is the circumradius of ABC.

5.  Show that any two points P and Q inside a regular n-gon can be joined by two circular arcs PQ which lie inside the n-gon and meet at an angle at least (1 - 2/n)π.

6.  The rectangle R is covered by a finite number of rectangles R₁, ... , R_n such that (1) each R_i is a subset of R, (2) the sides of each R_i are parallel to the sides of R, (3) the rectangles R_i have disjoint interiors, and (4) each R_i has a side of integral length. Show that R has a side of integral length.

7.  For each n > 0 we write (1 + 2^1/34 - 4^1/34)ⁿ as a_n + b_n 2^1/3 + c_n 4^1/3, where a_n, b_n, c_n are integers. Show that c_n is non-zero.

8.  Let C represent the complex numbers. Let g: C → C be an arbitrary function. Let w be a cube root of 1 other than 1 and let v be any complex number. Find a function f: C → C such that f(z) + f(wz + v) = g(z) for all z and show that it is unique.

9.  Define the sequence a₁, a₂, a₃, ... by 2ⁿ = the sum of a_d such that d divides n. Show that a_n is divisible by n. [For example, a₁ = 2, a₂ = 2, a₃ = 6.]

10.  There are n cars waiting at distinct points of a circular race track. At the starting signal each car starts. Each car may choose arbitrarily which of the two possible directions to go. Each car has the same constant speed. Whenever two cars meet they both change direction (but not speed). Show that at some time each car is back at its starting point.

11.  A quadrilateral has both a circumcircle and an incircle. Show that intersection point of the diagonals lies on the line joining the centers of the two circles.

12.  a, b, c, d, m, n are positive integers such that a² + b² + c² + d² = 1989, a + b + c + d = m² and the largest of a, b, c, d is n². Find m and n.

13.  The real numbers a₀, a₁, ... , a_n satisfy a₀ = a_n = 0, a_k = c + ∑_i=k^n-1 a_i-k(a_i + a_i+1). Show that c ≤ 1/(4n).

14.  Given 7 points in the plane, how many segments (each joining two points) are needed so that given any three points at least two have a segment joining them?

15.  Given a convex n-gon A₁A₂ ... A_n with area A and a point P, we rotate P through an angle x about A_i to get the point P_i. Find the area of the polygon P₁P₂ ... P_n.

16.  A positive integer is written in each square of an m x n board. The allowed move is to add an integer k to each of two adjacent numbers (whose squares have a common side). Find a necessary and sufficient condition for it to be possible to get all numbers zero by a finite sequence of moves.

17.  Show that the intersection of a plane and a regular tetrahedron can be an obtuse-angled triangle, but that the obtuse angle cannot exceed 120^o.

18.  Five points are placed on a sphere of radius 1. That is the largest possible value for the shortest distance between two of the points? Find all configurations for which the maximum is attained.

19.  a and b are non-square integers. Show that x² - ay² - bz² + abw² = 0 has a solution in integers not all zero iff x² - ay² - bz² = 0 has a solution in integers not all zero.

20.  b > 0 and a are fixed real numbers and n is a fixed positive integer. The real numbers x₀, x₁, ... , x_n satisfy x₀ + x₁ + ... + x_n = a and x₀² + ... + x_n² = b. Find the range of x₀.

21.  Let m > 1 be a positive odd integer. Find the smallest positive integer n such that 2¹⁹⁸⁹ divides mⁿ - 1.

22.  The points O, A, B, C, D in the plane are such that the six triangles OAB, OAC, OAD, OBC, OBD, OCD all have area at least 1. Show that one of the triangles must have area at least √2.

23.  155 birds sit on a circle center O. Birds at A and B are mutually visible iff ∠AOB ≤ 10^o. More than one bird may sit at the same point. What is the smallest possible number of mutually visible pairs?

24.  Given positive integers a ≥ b ≥ c, let N(a, b, c) be the number of solutions in positive integers x, y, z to a/x + b/y + c/z = 1. Show that N(a, b, c) ≤ 6ab(3 + ln(2a) ).

25.  ABC is an acute-angled triangle with circumcenter O and orthocenter H. AO = AH. Find all possible values for the ∠A.

There were 109 problems proposed in total, although this included one problems which was merely a variant. 32 were shortlisted (from which 6 were chosen and are not shown above, nor is the variant shown). 

Solutions

Problem 1

Ali Baba has a rectangular piece of carpet. He finds that if he lays if flat on the floor of either of his storerooms then each corner of the carpet touches a different wall of the room. He knows that the storerooms have widths 38 and 50 feet and the same (unknown but integral) length. What are the dimensions of the carpet?

 

Solution

Answer: 25 x 50.

Take the carpet to be EFGH and a storeroom to be ABCD, with E on AB, F on BC etc. Take HE = x, EF = y, AE = a, AH = b, DH = ka. Triangles AEH and CGF are congruent, and triangles BEF and DGH are congruent, and triangles AEH and BEF are similar. k is the similarity factor, so BE = DG = kb, BF = DH = ka. Also y = kx. AD is the unknown width q, AB = 38 or 50. Note that a, b take different values in the two cases, but x and y are the same. Hence k = y/x is also the same in the two cases.

Take AB = 50. Then a + kb = 50, ka + b = q. Hence kq - 50 = (k² - 1)a, 50k - q = (k² - 1)b. Similarly, if AB = 38, then kq - 38 = (k² - 1)a, 38k - q = (k² - 1)b. But x² = a² + b². So (kq - 50)² + (50k - q)² = (kq - 38)² + (38k - q)². So -100kq + 2500 + 2500k² - 100kq = -76kq + 1444 + 1444k² - 76kq. So 1056k² - 48kq + 1056 = 0, or 22k² - kq + 22 = 0, or kq = 22(1 + k²) (*)

We also have x²(k² - 1)² = (kq - 50)² + (50k - q)² = (k² + 1)(q² + 2500) - 200kq = (k² + 1)(q² - 1900), using (*).

So x²(k² - 1)k² = (k² + 1)( (22k² + 22)² - 1900k²), using (*), = (k² + 1)(484k⁴ - 932k² + 484). If we divide by k⁸ and put k' = 1/k, we get the same equation for k'. So if k is a solution, then 1/k is also a solution.

k = y/x, which is rational. Put k = c/d, where c and d are coprime integers. Then we get x²c²(c² - d²)² = c²(484c⁴ - 448c²d² - 448d⁴) + 484d⁶. Hence c² divides 484d⁶. But c and d are coprime, so c must divide 22. Since k' is also a solution of the equation, d must also divide 22. So each of c, d is one of 1, 2, 11, 22. That implies k must be 1, 2, 1/2, 11, 1/11, 22, 1/22, 2/11 or 11/2. But k and 1/k give the same solution (with x and y interchanged), so we need only consider k = 1, 2, 11, 22, 11/2.

k = 1 does not work (substituting into the equation for x, we get 0 = 1).

k = 2 gives (from 22k² - kq + 22 = 0), q = 55, then x = 25 (from the equation for x) and then y = 50.

k = 11 gives q = 244 = 4.61. But consider x²(k² - 1)² = (k² + 1)(q² - 1900). It is easy to check that 61 divides rhs, but not 61², so the rhs is not a square. Contradiction (since the lhs is a square). So k = 11 does not give a solution.

k = 22 gives q = k² + 1 = 485 = 5.97. So we have the same argument with 97 instead of 61, and k = 22 does not give a solution.

k = 11/2 gives q = 125, k² + 1 = 125/4, k² - 1 = 117/4. So we get x²117² = 4.5⁵(25² - 76). But 5 divides the rhs to an odd power, so k = 11/2 does not give a solution. 

Problem 2

Prove that for n > 1 the polynomial xⁿ/n! + x^n-1/(n-1)! + ... + x/1! + 1 has no rational roots.

 

Solution

Let p be any prime. We show first that p^k does not divide k! Take m so that p^m ≤ k < p^m+1. Then the highest power of p dividing k! is p^r, where r = [k/p] + [k/p²] + [k/p³] + ... + [k/p^m] ≤ k/p + k/p² + ... + k/p^m = k(1 - 1/p^m)/(p - 1) < k.

Suppose there is a rational root x of the polynomial. Put x = a/b, where a and b are coprime integers. Then aⁿ + na^n-1b + ... + (n-1)! a b^n-1 + n! bⁿ = 0. So aⁿ must be divisible by b. But a and b are coprime, so b must be 1, in other words, the root must be an integer.

Now take p to be a prime dividing n. Then p must divide aⁿ and hence a. But we have - n! = n! (aⁿ/n! + a^n-1/(n-1)! + ... + a¹/1! ). Each term inside the parentheses is divisible by p, because p^k divides a^k but not k! So a higher power of p divides the rhs than the lhs. Contradiction.

Problem 3

The polynomial xⁿ + n x^n-1 + a₂x^n-2 + ... + a₀ has n roots whose 16th powers have sum n. Find the roots.

 

Solution

Answer: all the roots are -1.

Suppose the roots are r₁, r₂, ... , r_n. Note that ∑ r_i = -n. Applying Cauchy to 1, r_i, we have
n² = |∑ r_i|² ≤ (∑ 1²) |∑ r_i²|, so |∑ r_i²| ≥ n.

Applying Cauchy to 1, r_i², we have:
n² ≤ |∑ r_i²|² ≤ ∑ 1² |∑ r_i⁴|, so |∑r_i⁴ ≥ n.

Similarly, applying Cauchy to 1, r_i⁴, we have:
n² ≤ |∑ r_i⁴|² ≤ n |∑ r_i⁸|, so |∑ r_i⁸| ≥ n.

Finally, applying Cauchy to 1, r_i⁸, we have:
n² ≤ |∑ r_i⁸| ≤ n |∑ r_i¹⁶|, so |∑ r_i¹⁶| ≥ n.

But |∑ r_i¹⁶| = n. Hence all the above inequalities are equalities. So, particular, |∑ r_i²| = n. We have equality in Cauchy iff the ratio of the corresponding terms is equal. Hence, considering the first inequality, we must have all r_i equal. Hence all the roots are -1.

Problem 4

The angle bisectors of the triangle ABC meet the circumcircle again at A'B'C'. Show that 16 (area A'B'C')³ ≥ 27 area ABC R⁴, where R is the circumradius of ABC.

 

Solution

Let R be the circumradius and O the circumcircle. ∠BOC = 2 ∠A, so area BOC = ½ R² sin 2A. Hence area ABC = ½ R²(sin 2A + sin 2B + sin 2C).

∠A'C'C = ∠A'AC = ∠A/2, and ∠B'C'C = ∠B'BC = ∠B/2, so ∠A'C'B' = ∠A/2 + ∠B/2. The circumradius is the same, so area A'B'C' = ½ R²(sin(A+B) + sin(B+C) + sin(C+A) ). Thus we have to show that 4 (sin(A+B) + sin(B+C) + sin(C+A) )³ ≥ 27 (sin 2A + sin 2B + sin 2C).

Applying AM/GM to sin(A+B), sin(B+C), sin(C+A) we get (sin(A+B) + sin(B+C) + sin(C+A) )³ ≥ 27 sin(A+B) sin(B+C) sin(C+A).

We now need some straightforward applications of the forumulae for sin(x+y), cos(x+y) etc. We have sin(B+C) sin(C+A) = (cos(B-A) - cos(C+180) )/2 = (cos(B-A) + cos C)/2, so sin(A+B) sin(B+C) sin(C+A) = ½ sin(A+B) cos(B-A) + ½ sin(A+B) cos C. But sin 2A + sin 2B = sin( (A+B) + (B-A) ) + sin( (A+B) - (B--A) ) = 2 sin(A+B) cos(B-A), and sin( (A+B) + C) + sin( (A+B) - C) = 2 sin(A+B) cos C, so sin(A+B) sin(B+C) sin(C+A) = ¼ (sin 2A + sin 2B + sin(A+B-C) ) = ¼ (sin 2A + sin 2B + sin 2C). Hence (sin(A+B) + sin(B+C) + sin(C+A) )³ ≥ (27/4) (sin 2A + sin 2B + sin 2C), as required. 

Problem 6

The rectangle R is covered by a finite number of rectangles R₁, ... , R_n such that (1) each R_i is a subset of R, (2) the sides of each R_i are parallel to the sides of R, (3) the rectangles R_i have disjoint interiors, and (4) each R_i has a side of integral length. Show that R has a side of integral length.

 

Solution

Take one of the vertices of R to be at a lattice point. Now count pairs (v, S), where v is a lattice point, S is a small rectangle and v is a vertex of S. A small rectangle S must either have 2 or 4 vertices which are lattice points, so summing over S, the number of pairs is even. The four vertices of R are each vertices of just one small rectangle, but any other vertex must be a vertex of 2 or 4 small rectangles. So summing over v, the total has the same parity as the number of vertices of R which are lattice points. Hence an even number of vertices of R are lattice points. But at least one is a lattice point, so at least two are lattice points. Hence R has at least one side of integral length. 

Problem 8

Let C represent the complex numbers. Let g: C → C be an arbitrary function. Let w be a cube root of 1 other than 1 and let v be any complex number. Find a function f: C → C such that f(z) + f(wz + v) = g(z) for all z and show that it is unique.

 

Solution

(1) f(z") + f(wz"+v) = g(z"), so taking z" = wz' + v, we get
(2) f(wz'+v) + f(w²z'+wv+v) = g(wz'+v), and taking z' = wz + v, we get
(3) f(w²z+wv+v) + f(z) = g(w²z+wv+v) Taking (1) - (2) + (3) with (with z" and z' as z) we get:
2 f(z) = g(z) - g(wz + v) + g(w²z + wv + v).

Problem 9

Define the sequence a₁, a₂, a₃, ... by 2ⁿ = the sum of a_d such that d divides n. Show that a_n is divisible by n. [For example, a₁ = 2, a₂ = 2, a₃ = 6.]

 

Solution

Let b_n be the number of sequences of length n, made up of 0s and 1s, which cannot be divided into more than one identical block. Then b_n satisfies the same recurrence relation as a_n and has the same initial values. So they are the same. But b_n must be divisible by n, because we can divide the non-repeating sequences of length n into groups of n, where the sequences in each group are obtained from each other by cyclic shifts.

 

Problem 10

There are n cars waiting at distinct points of a circular race track. At the starting signal each car starts. Each car may choose arbitrarily which of the two possible directions to go. Each car has the same constant speed. Whenever two cars meet they both change direction (but not speed). Show that at some time each car is back at its starting point.

 

Solution

Label the cars 1 to n according to their starting positions (so we label any car 1 and then go round the track clockwise, labeling the next car 2, the next 3 and so on). If two cars swapped labels whenever they met, then the labels would move at constant speed without ever changing direction. Suppose the car speed is v and the track length is vT, then after time T the labels would all be in their original positions.

Now suppose there is no label swapping. The order of the labels can never change. At time T, there is a car at each initial position, so the labeling of the cars must be a rotation of the initial labeling. Hence after time nT, the cars must be back in their initial positions.

 Problem 12

a, b, c, d, m, n are positive integers such that a² + b² + c² + d² = 1989, a + b + c + d = m² and the largest of a, b, c, d is n². Find m and n.

 

Solution

Answer: m = 9, n = 6.

7⁴ = 2401 > 1989, so n < 7. We have 4² = 16 and 4 x 16² = 1024 < 1989, so n > 4. Hence n = 5 or 6. Assume a ≥ b ≥ c ≥ d, so a = n².

k has the same parity as k². But a² + b² + c² + d² = 1989 is odd, so a + b + c + d = m² is odd. If n = 36, then b² + c² + d² = 693, so by Cauchy, (b + c + d)² ≤ 3.693. Hence b + c + d ≤ 45. Hence 36 < m² ≤ 81 and m² is odd, so m = 7 or 9. Similarly, if n = 25, then b² + c² + d² = 1364 and so by Cauchy b + c + d < 64. Hence again m = 7 or 9.

Suppose first that m = 7. Then (49 - a)² = (b + c + d)² > b² + c² + d² = 1989 - a², so a² - 49a + 206 > 0. Put f(x) = x² - 49x + 206. We can easily check that f(4) = f(45) = 26, f(5) = f(44) = -14, so f(x) < 0 for 5 ≤ x ≤ 44. But we know that a must be 25 or 36, so there are no solutions with m = 7. Hence m = 9.

It is easy to check that we do have a solution for m = 9, n = 6: 12 + 15 + 18 + 36 = 9² and 12² + 15² + 18² + 36² = 1989.

Finally, suppose m = 9, n = 5. Then b + c + d = 56, b² + c² + d² = 1364. Put b = 25 - B, c = 25 - C, d = 25 - D, where B, C, D are non-negative. So B + C + D = 19, B² + C² + D² = 1364 - 1875 + 50.19 = 439. But now B² + C² + D² > (B + C + D)². Contradiction. So there are no solutions with m = 9, n = 5. 

Problem 13

The real numbers a₀, a₁, ... , a_n satisfy a₀ = a_n = 0, a_k = c + ∑_i=k^n-1 a_i-k(a_i + a_i+1). Show that c <= 1/(4n).

 

Solution

This is awkward, because it is not easy to get an expression for any a_i in terms of c (apart from i = 0, n-1, n). The key is not to try!

Put s_k = a₀ + a₁ + ... + a_k. Then we have s_n = s_n-1 = ∑_k=0..n-1 (c + ∑_i=k..n-1 a_i-k(a_i + a_i+1) ) = nc + ∑_i=0..n-1 (a_i + a_i+1) ∑_k=0..i a_k. (As usual, inverting the order of summation requires a little care, but is basically straightforward. Just check the low and high values.). So s_n = nc + ∑_i=0..n-1 (a_i + a_i+1) s_i = (s₂ - s₀)s₁ + (s₃ - s₁)s₂ + (s₄ - s₂)s₃ + ... + (s_n - s_n-2)s_n-1 = s_ns_n-1 (we have s₀ = 0 and the other terms cancel in pairs) = s_n².

So nc = s_n - s_n² = ¼ - (s_n - ½)² ≤ ¼. Hence c ≤ 1/4n. 

Problem 14

Given 7 points in the plane, how many segments (each joining two points) are needed so that given any three points at least two have a segment joining them?

 

Solution

Answer: 9.

9 is obviously sufficient. Take points A, B, C and P, Q, R, S with segments AB, BC, CA, and PQ, PR, PS, QR, QS, RS. If the three points are A, B, C or three of P, Q, R, S, then they are all joined. Any other three points must include either two from A, B, C (which will be joined) or two from P, Q, R, S (which will be joined).

Now suppose we have only 8 points. Suppose that we cannot find three points without a segment between them. If every point is joined to at least three others, then there are at least 7.3/2 segments. Contradiction. So there is a point A which is not joined to any of B, C, D, E. If two of B, C, D, E are not joined, then with A they form three points with no segments. Contradiction. So there are 6 segments between B, C, D, E.

Let the remaining two points be X, Y. Two of the points A, X, Y cannot be joined (because there are only 2 segments available outside B, C, D, E). One of the points B, C, D, E cannot be joined to either of these two points (since there are at most 2 segments available), so we have three points with no segments. Contradiction.

Problem 15

Given a convex n-gon A₁A₂ ... A_n with area A and a point P, we rotate P through an angle x about A_i to get the point P_i. Find the area of the polygon P₁P₂ ... P_n.

 

Solution

Consider the triangle PA_iP_i. The angle A_iPP_i is 90^o - x/2, which is independent of i, and the ratio PP_i/PA_i = 2 sin x/2, which is also independent of i. So we can obtain P_i by rotating A_i through an angle 90^o - x/2 about P and then expanding by a factor 2. Thus the area of the polygon P₁P₂ ... P_n is 4 sin²(x/2) times the area of the polygon A₁A₂ ... A_n. 

Problem 16

A positive integer is written in each square of an m x n board. The allowed move is to add an integer k to each of two adjacent numbers (whose squares have a common side). Find a necessary and sufficient condition for it to be possible to get all numbers zero by a finite sequence of moves.

 

Solution

Answer: color the squares alternately black and white as on a chessboard. We can get all zeros iff the sum of the numbers on the black squares equals the sum of the numbers on the white squares.

The condition is clearly necessary, because if ∑_black denotes the sum of the numbers on the black squares and ∑_white the sum of the numbers on the white squares, then ∑_black - ∑_white is invariant.

So suppose the condition holds. By adding enough to every adjacent pair in the second row, we can ensure that each number in the second row is at least as large as the integer above it in the first row. Then for each integer in the first row subtract it from itself and the integer below. That zeros the first row. Similarly, we can zero each row except the bottom row.

We now work along the bottom row in a similar way. We start by adding enough to the integers in columns 2 and 3, so that the number in column 2 is at least as large as the number in column 1. Then subtract the number in column 1 from that in column 1 and column 2, thus zeroing the number in column 1. In this way we zero all except the last two numbers in the row. But by the invariant they must be equal, so we can zero them both simultaneously.

Problem 17

Show that the intersection of a plane and a regular tetrahedron can be an obtuse-angled triangle, but that the obtuse angle cannot exceed 120^o.

 

Solution

We may take one vertex of the tetrahedron to be the origin, and one edge to lie along the x-axis, another along the vector (1, √3, 0) and the third along the vector (1, 1/√3, √(8/3) ). There is no loss of generality in assuming that one vertex of the triangle lies on each of these edges, and indeed we may take one vertex to be P = (2, 0, 0). So the others are Q = h (1, √3, 0) and R = k (1, 1/√3, √(8/3) ) with h, k > 0.

So PQ² = (2 - h)² + 3h² = 4 - 4h + 4h², PR² = (2 - k)² + k²/3 + 8k²/3 = 4 - 4k + 4k², QR² = (h - k)² + (h√3 - k/√3)² + 8k²/3 = 4h²/3 - 4hk + 4k².

Note also that OP² = 4, OQ² = 4h², OR² = 4k². So if h = k = 1, then all of OP, OQ, OR, PQ, PR, QR have length 2, which proves that the vectors above were correctly chosen.

The cosine formula gives cos P = (PQ² + PR² - QR²)/(2 PQ.PR) = (1 - h + h² + 1 - k + k² - h² + hk - k²)/(2 √(1 - h + h²)√(1 - k + k² ) = (1 + (h - 1)(k - 1) )/(2 √(1 - h + h²)√(1 - k + k² ).

For an obtuse angle we require cos P < 0, so one of h, k is greater than 1 and the other is less than 1. Without loss of generality h < 1, k > 1. Clearly, we can get cos P < 0. For example, h = 1/3, k = 3 gives cos P = -1/7.

(h - 1) > -1, so for cos P < 0 we need k > 2. As P increases from 90^o to 180^o, cos P decreases from 0 to -1, and cos 120^o = -1/2, so it is sufficient to show that (h + k - hk - 2)² < (1 - h + h²)(1 - k + k²) or that hk² + (h² - 5h + 3)k - 3 + 3h > 0 for 0 < h < 1 and k > 2. We can regard this as a quadratic in k. By completing the square, we see that its minimum value is when k = - (h² - 5h + 3)/2h. Certainly this is less than 2, because - (h² - 5h +3 ) < 4h or h² - h + 3 > 0 for 0 < h < 1. So the quadratic is an increasing function of k for k >= 2. Hence is value for k > 2 is greater than its value at k = 2 which is 4h + 2h² - 10h + 6 - 3 + 3h = 3 - 3h + 2h² > 3(1 - h) > 0.

Note that if we take h small and k large, then cos P is roughly -(k-2)/2k, so we can get close to 120^o. 

Problem 18

Five points are placed on a sphere of radius 1. That is the largest possible value for the shortest distance between two of the points? Find all configurations for which the maximum is attained.

 

Solution

Answer: √2. All maximal configurations have two points at opposite ends of a diameter. The other three points lie on the great circle midway between these two points (such that the distance between any two is at least √2).

Suppose the points are such that the distance between any two is at least √2. Then any two must subtend an angle of at least 90^o at the center of the sphere. We claim that two of the points must be at opposite ends of a diameter. Let S be one of the points. Take it at the south pole. So suppose that none of the points is at the north pole N. If the other 4 points all lie on the equator, then they must be equally spaced and so a pair lie at opposite ends of a diameter as claimed.

If there is a point X not on the equator, then take a line of longitude L₁ through it. Now take three other lines of longitude L₂, L₃, L₄, so that the 4 lines are equally spaced. They divide the northern hemisphere into 4 equal quadrants (which overlap along the lines of longitude). Each quadrant is a curvilinear triangle with three vertices. Clearly, if no two points in the same quadrant subtend an angle of more than 90^o at the center, and if they subtend an angle of 90^o, then one must be a vertex and the other must be on the opposite (curvilinear) side. Thus (1) the minimum angle is at least 90^o, and (2) each of the two quadrants containing X must contain another of the 4 points (apart from X) and they must lie at P and P'. But now P and P' are opposite ends of a diameter.

Now if 2 of the 5 points are opposite ends of a diameter, and the minimum distance is at least √2, then the other three points must lie on the great circle midway between. 

Problem 19

a and b are non-square integers. Show that x² - ay² - bz² + abw² = 0 has a solution in integers not all zero iff x² - ay² - bz² = 0 has a solution in integers not all zero.

 

Solution

Obviously if there is a not-all-zero integral solution to x² - ay² - bz² = 0, then it is also a not-all-zero integral solution to x² - ay² - bz² + abw² = 0.

Now suppose that x, y, z, w is a not-all-zero integral solution to x² - ay² - bz² + abw² = 0. Then we have (x² - ay²) - b(z² - aw²) = 0 and hence (x² - ay²)(z² - aw²) - b(z² - aw²)² = 0. But (x² - ay²)(z² - aw²) = (xz - ayw)² - a(yz - xw)², so X² - aY² - bZ² = 0, where X = xz - ayw, Y = yz - zw, Z = z² - aw². It remains to show that X, Y, Z are not all zero.

If Z = 0, then since a is a non-square, we must have w = z = 0. Hence x² - ay² = 0, so x = y = 0. Contradiction. So Z must be non-zero.

Problem 20

b > 0 and a are fixed real numbers and n is a fixed positive integer. The real numbers x₀, x₁, ... , x_n satisfy x₀ + x₁ + ... + x_n = a and x₀² + ... + x_n² = b. Find the range of x₀.

 

Solution

By Cauchy we have (∑ x_i)² ≤ n ∑ x_i² (for n terms) (*). Hence if x₀ = x, then (a - x)² ≤ n(b - x²) or (n+1) x² - 2ax + a² - nb ≤ 0.

If a² < (n+1)(a² - nb), or (n+1)b < a², then the quadratic is always positive, so there are no possible values for x₀. If a² = (n+1)b, then the only possible value of x₀ is a/(n+1). If a² < (n+1)b, then x₀ must lie between a/(n+1) + (1/(n+1) )√( n(n+1)b - na²) and a/(n+1) - (1/(n+1) )√( n(n+1)b - na²).

We get equality in the Cauchy inequality (*) iff all the terms x_i are equal. So all the values in the range given above can be achieved by taking x_i = (a - x₀)/n for i > 0.

Problem 22

The points O, A, B, C, D in the plane are such that the six triangles OAB, OAC, OAD, OBC, OBD, OCD all have area at least 1. Show that one of the triangles must have area at least √2.

 

Solution

Take OA = a, OB = b, OC = c, OD = d, ∠AOB = x, ∠BOC = y, ∠COD = z, with the configuration as shown. Now we have:
|OAB| = ab |sin x|
|OBC| = bc |sin y|
|OCD| = cd |sin z|
|OAC| = ac |sin(x+y)|
|OAD| = ad |sin(x+y+z)|
|OBD| = bd |sin(y+z)|

But 2 sin(x+y+z) sin y + 2 sin x sin z = cos(x+z) - cos(x+2y+z) + cos(x-z) - cos(x+z) = cos(x-z) - cos(x+2y+z) = 2 sin(x+y) sin(y+z). So multiplying through by abcd/2 we get ± |OAB| |OCD| ± |OBC| |OAD| ± |OAC| |OBD| = 0. Two of the signs must be the same. So we get that the product of two of the areas equals the sum of two other area products and hence is at least 2. Hence one of the two areas in the product must be at least √2. 

Problem 23

155 birds sit on a circle center O. Birds at A and B are mutually visible iff ∠AOB ≤ 10^o. More than one bird may sit at the same point. What is the smallest possible number of mutually visible pairs?

 

Solution

Answer: 270. Take 35 equally spaced points around the circle and place 5 birds at each of 15 points and 4 birds at the other 20 points. Only birds at the same point are mutually visible, so there are 15.10 + 20.6 = 270 mutually visible pairs.

Suppose bird P is at A and bird Q is at B, where A and B are distinct but ∠AOB ≤ 10^o. Suppose that h birds are visible from A not B, and that k birds are visible from B not A. Without loss of generality h ≤ k. Now suppose all the birds at B move to A. Then the number of mutually visible pairs will not increase. By repeating this operation, we get to a configuration where two birds can see each other only if they are at the same point. Since the number of pairs has not been increased, it is sufficient to consider configurations where two birds can only see ach other if they are at the same point.

Thus we may take 35 positions, labeled 1, 2, 3, ... , 35 and place x_i birds at position i (we allow x_i to be 0). So we wish to minimise ½ ∑ x_i(x_i - 1), or equivalently ∑ x_i², subject to ∑ x_i = 155. Suppose two of the x_i differ by more than 1, without loss of generality x₁ > x₂ + 1. Then (x₁² + x₂²) - ( (x₁ - 1)² + (x₂ + 1)²) = 2(x₁ - x₂ - 1) > 0. So in a minimising set of x_i, the values can differ by at most 1. Thus the minimum is attained when 20 values equal 4 and 15 values equal 5.

Problem 25

ABC is an acute-angled triangle with circumcenter O and orthocenter H. AO = AH. Find all possible values for the angle A.

 

Solution

Let the altitude from C be CF and the circumradius be R. ∠HAF = 90^o - B, so AF = AH sin B = R sin B. Hence CF = R sin B tan A. But ∠BOC = 2A, so BC = 2 R sin A, and CF = BC sin B = 2R sin A sin B. Hence cos A = ½. Hence A = 60^o.

Read more »

Posted in: IMO shortlist

29th IMO 1988 shortlisted Problems & Solutions

1.  The sequence a₀, a₁, a₂, ... is defined by a₀ = 0, a₁ = 1, a_n+2 = 2a_n+1 + a_n. Show that 2^k divides a_n iff 2^k divides n.

2.  Find the number of odd coefficients of the polynomial (x² + x + 1)ⁿ.

3.  The angle bisectors of the triangle ABC meet the circumcircle again at A', B', C'. Show that area A'B'C' ≥ area ABC.

4.  The squares of an n x n chessboard are numbered in an arbitrary manner from 1 to n² (every square has a different number). Show that there are two squares with a common side whose numbers differ by at least n.

6.  ABCD is a tetrahedron. Show that any plane through the midpoints of AB and CD divides the tetrahedron into two parts of equal volume.

7.  c is the largest positive root of x³ - 3x² + 1. Show that [c¹⁷⁸⁸] and [c¹⁹⁸⁸] are multiples of 17.

8.  u₁, u₂, ... , u_n are vectors in the plane, each with length at most 1, and with sum zero. Show that one can rearrange them as v₁, v₂, ... , v_n so that all the partial sums v₁, v₁ + v₂, v₁ + v₂ + v₃, ... , v₁ + v₂ + ... + v_n have length at most √5.

10.  Let X = {1, 2, ... , n}. Find the smallest number of subsets f(n) of X with union X such that given any distinct a, b in X, one of the subsets contains just one of a, b.

11.  The lock on a safe has three wheels, each of which has 8 possible positions. It is known that the lock is defective and will open if any two wheels are in the correct position. How many combinations must be tried to guarantee opening the safe?

12.  ABC is a triangle. K, L, M are points on the sides BC, CA, AB respectively. D, E, F are points on the sides LM, MK, KL respectively. Show that (area AME)(area CKE)(area BKF)(area ALF)(area BDM)(area CLD) ≤ (1/8 area ABC)⁶.

14.  For what values of n, does there exist an n x n array of entries 0, ±1 such that all rows and columns have different sums?

15.  ABC is an acute-angled triangle. H is the foot of the perpendicular from A to BC. M and N are the feet of the perpendiculars from H to AB and AC. L_A is the line through A perpendicular to MN. L_B and L_C are defined similarly. Show that L_A, L_B and L_C are concurrent.

17.  ABCDE is a convex pentagon such that BC, CD and DE are equal and each diagonal is parallel to a side (AC is parallel to DE, BD is parallel to AE etc). Show that the pentagon is regular.

19.  f has positive integer values and is defined on the positive integers. It satisfies f( f(m) + f(n) ) = m + n for all m, n. Find all possible values for f(1988).

20.  Find the smallest n such that if {1, 2, ... , n} is divided into two disjoint subsets then we can always find three distinct numbers a, b, c in the same subset with ab = c.

21.  49 students solve a set of 3 problems. Each problem is marked from 0 to 7. Show that there are two students A and B such that A scores at least as many as B for each problem.

22.  Show that there are only two values of N for which (4N+1)(x₁² + x₂² + ... + x_N²)= 4(x₁ + x₂ + ... + x_N)² + 4N + 1 has an integer solution x_i.

23.  I is the incenter of the triangle ABC. Show that for any point P, BC·PA² + CA·PB² + AB·PC² = BC·IA² + CA·IB² + AB·IC² + (AB + BC + CA)·IP².

24.  x₁, x₂, x₃, ... is a sequence of non-negative reals such that x_n+2 = 2x_n+1 - x_n and x₁ + x₂ + ... + x_n ≤ 1 for all n > 0. Show that x_n+1 ≤ x_n and x_n+1 > x_n - 2/n² for all n > 0.

25.  A double number has an even number of digits and the first half of its digits are the same as the second half. For example, 360360 is a double number, but 36036 is not. Show that infinitely many double numbers are squares.

27.  ABC is an acute-angled triangle area S. L is a line. The lengths of the perpendiculars from A, B, C to L are u, v, w respectively. Show that u²tan A + v²tan B + w²tan C ≥ 2S. For which L does equality occur?

28.  The sequence of integers a₁, a₂, a₃, ... is defined by a₁ = 2, a₂ = 7, and -1/2 < a_n+2 - a_n+1²/a_n ≤ 1/2. Show that a_n is odd for n > 1.

29.  n signals are equally spaced along a rail track. No train is allowed to leave a signal whilst there is a moving train between that signal and the next. Any number of trains can wait at a signal. At time 0, k trains are waiting at the first signal. Except when waiting at a signal each train travels at a constant speed, but each train has a different speed. Show that the last train reaches signal n at the same time irrespective of the order in which the trains are arranged at the first signal.

30.  ABC is a triangle. M is a point on the side AC such that the inradii of ABM and CBM are the same. Show that BM² = cot(B/2) area ABC.

31.  An even number of people have a discussion sitting at a circular table. After a break they sit down again in a different order. Show that there must be two people with the same number of people sitting between them before and after the break.

Note: problems 5, 9, 13, 16, 18 and 26 were used in the Olympiad and are not shown here. 

Solutions

Problem 1

The sequence a₀, a₁, a₂, ... is defined by a₀ = 0, a₁ = 1, a_n+2 = 2a_n+1 + a_n. Show that 2^k divides a_n iff 2^k divides n.

Solution

Since a_n+2 = a_n mod 2, and a₁ is odd, it follows that a_odd is always odd. Define b_n by the same recurrence relation with b₀ = b₁ = 2. Then obviously all b_n are even, so b_n+2 = b_n mod 4 and hence b_n = 2 mod 4 for all n.

Solving, we find a_n = (1 + √2)ⁿ/√8 - (1 - √2)ⁿ/√8, and b_n = (1 + √2)ⁿ + (1 - √2)ⁿ. Hence a_nb_n = a_2n. The required result is now a trivial induction on k. 

Problem 2

Find the number of odd coefficients of the polynomial (x² + x + 1)ⁿ.

Answer In binary n is a block of a₁ 1s, followed by a block of 0s, followed by a block of a₂ 1s, followed by a block of 0s, ... , followed by a block of a_k 1s, (followed by a block of 0s). Let f(x) = (2^x+2 + (-1)^x+1)/3. Then the number of odd coefficients is ∏ f(a_i).

Solution

Let c(n) be the number of odd coefficients. Obviously c(1) = 3. We have (x² + x + 1)² = x⁴ + x² + 1 mod 2. Hence by a trivial induction c(2^k) = 3.

It is convenient to consider the expansion of (x + 1 + 1/x)ⁿ which obviously has the same number of odd coefficients. We guess that for n = 2^k - 1 and k odd, we have (x + 1 + 1/x)ⁿ = (xⁿ + x^n-1 + x^n-3 + x^n-4 + x^n-6 + ... + x + 1 + 1/x + ... + 1/xⁿ) mod 2 (missing out every third term), and for k even we have (x + 1 + 1/x)ⁿ = (xⁿ + x^n-1 + x^n-3 + x^n-4 + x^n-6 + ... + x² + 1 + 1/x² + ... + 1/xⁿ) mod 2 (missing out every third term for the positive powers, but including x⁰ and then matching negative powers).

We prove this by induction on k. It is true for k = 1 and 2. Suppose it is true for k-1 odd and k even. If n = 2^k - 1, then 2^k+1 - 1 = 2n+1, and (x + 1 + 1/x)²ⁿ⁺¹ = (x + 1 + 1/x) (x + 1 + 1/x)²ⁿ = (x + 1 + 1/x) (x² + 1 + 1/x²)ⁿ mod 2 = x(x² + 1 + 1/x²)ⁿ + (x² + 1 + 1/x²)ⁿ + (1/x)(x² + 1 + 1/x²)ⁿ. By induction this is:

x2n+1 + x2n-1 + x2n-5 + x2n-7 + ... + x7 + x5 + x + 1/x3 + 1/x5 + 1/x9 + ... + 1/x2n-1
    x2n + x2n-2 + x2n-6 + x2n-8 + ... + x6 + x4 + 1 + 1/x4 + 1/x6 + 1/x10 + ... + 1/x2n
        x2n-1 + x2n-3 + x2n-7 + x2n-9 + ... + x5 + x3 + 1/x + 1/x5 + 1/x7 + 1/x11 + ... 

+ 1/x2n+1
giving
x2n+1 + x2n + x2n-2 + x2n-3 + x2n-5 + x2n-6 + ... + x7 + x6 + x4 + x3 + x + 1 + 1/x + 1/x3 + 1/x4 + 

... + 1/x2n + 1/x2n+1

So the result is true for k+1. In an exactly similar way, we deduce that the result is true for k+2 and hence for all k. It follows immediately that c(2^k - 1) = (2^k+2 + (-1)^k+1)/3.

Now if n = 2^k+1M + N with N < 2^k, then putting K = 2^k+1 to cope with the deficiencies of the browser (or maybe of my knowledge of HTML) we have (x² + x + 1)ⁿ = (x² + x + 1)^KM(x² + x + 1)^N = (x^2K + x^K + 1)^M(x² + x + 1)^N. But the highest power in (x² + x + 1)^N is x^2N and 2N < K. So if A is the expansion of (x^2K + x^K + 1)^M and B is the expansion of (x² + x + 1)^N, then each power in the product A times B occurs in only one way. Hence c(n) = c(M) c(N). Hence the answer given at the start of the solution. 

Problem 3

The angle bisectors of the triangle ABC meet the circumcircle again at A', B', C'. Show that area A'B'C' ≥ area ABC.

Solution

Let H be the orthocenter. Let AH meet the circumcircle at A". Define B" and C" similarly. ∠A"CB = ∠A"AB = 90^o - ∠B = ∠BCH, and A"H is perpendicular to BC. Hence A" is the reflection of H in BC and so triangles A"CB and HCB are congruent. Similarly for C"BA and B"AC. So the hexagon AB"CA"BC" has twice the area of ABC.

Let B'C' meet AA' at X. Then ∠B'XA = ∠B'C'A + ∠XAC' = ∠B'C'A + ∠XAB + ∠C'AB = ∠B'BA + ∠A'AB + ∠C'CB = ∠B/2 + ∠A/2 + ∠C/2 = 90^o. Hence A'A is an altitude of the triangle A'B'C'. Hence the hexagon AB'CA'BC' has twice the area of the triangle A'B'C'.

But A' is the midpoint of the arc BC, so area A'BC ≥ area A"BC. Similarly for the other two pairs of triangles, so area AB'CA'BC' ≥ area AB"CA"BC". Hence area A'B'C' ≥ area ABC.

 

Problem 4

The squares of an n x n chessboard are numbered in an arbitrary manner from 1 to n² (every square has a different number). Show that there are two squares with a common side whose numbers differ by at least n.

Solution

For k = 1, 2, 3, ... , n² - n, we may partition {1, 2, 3, ... , n²} into the three non-empty sets A_k = {1, 2, 3, ... , k}, B_k = {k+1, k+2, ... , k+n-1}, C_k = {k+n, k+n+1, ... , n²}.

Call two squares adjacent if they share a side. Suppose an arrangement is possible with the numbers in adjacent squares always differing by less than n. Since B_k has less than n elements, we can choose a row and a column which do not contain an element of B_k. Their union is the cross X_k. If X_k contains an element of A_k and an element of C_k, then it must contain two elements in adjacent squares, one in A_k and one in C_k. Contradiction (because these elements must differ by at least n). So X_k is either a subset of A_k or a subset of C_k.

Since A₁ only has one element, X₁ must be a subset of C₁. Similarly, since C_N only has one element, X_N must be a subset of A_N (where N = n² - n). Hence for some k, X_k is a subset of C_k and X_k+1 is a subset of A_k+1. But any two crosses have at least two elements in common, whereas A_k+1 and C_k are disjoint. Contradiction.

Problem 6

ABCD is a tetrahedron. Show that any plane through the midpoints of AB and CD divides the tetrahedron into two parts of equal volume.

Solution

Let M be the midpoint of AB, and N the midpoint of CD. Let p be the plane through AB parallel to CD. Any plane p' parallel to p which intersects the segment MN will intersect the tetrahedron in a parallelogram with center on the line MN. Any plane q through MN will pass through the center of the parallelogram and hence divide it into two equal parts. So suppose q divides the tetrahedron into two parts T and T'. We have established that the area of the intersection of p' and T is equal to the area of the intersection of p' and T'. It follows from Cavalieri's principle that T and T' have equal volume. (This is obvious if you are happy to obtain the volume by integration.)

(To see that PQRS is a parallelogram, note that PQ is parallel to CD, and RS is parallel to CD, so PQ and RS are parallel. Similarly QR and PS are parallel to AB and hence to each other.) 

Problem 7

c is the largest positive root of x³ - 3x² + 1. Show that [c¹⁷⁸⁸] and [c¹⁹⁸⁸] are multiples of 17.

Solution

Put f(x) = x³ - 3x² + 1. Let the roots be a < b < c. We have f(-1) = -3, f(-½) = 1/8, f(½) = 3/8, f(1) = -1, f(2√2) = 16√2 - 23 < 0, f(3) = 1. Hence -1 < a < -½, ½ < b < 1, 2√2 < c < 3. Hence |a|, |b| < 1. Also a + b + c = 3, so a + b = 3 - c > 0, so |a| < |b|. Hence |a|ⁿ < |b|ⁿ. But b > 0, so aⁿ + bⁿ > 0. Finally, a² + b² = (a + b)² - 2ab = (3 - c)² + 2/c = 9 - 6c + c² + 2/c. But c³ - 3c + 1 = 0, so -6c + c² + 2/c = -c². Hence a² + b² = 9 - c² < 1. Hence aⁿ + bⁿ < 1 for all n > 1.

Put u_n = aⁿ + bⁿ + cⁿ. Then u₀ = 3, u₁ = 3, u₂ = (a + b + c)² - 2(ab + bc + ca) = 9 and u_n+3 = 3u_n+2 - u_n. Hence u_n is an integer for all n. Hence [cⁿ] = u_n - 1.

Working mod 17, we have u₀ = 3, u₁ = 3, u₂ = 9. Hence u₃ = 3·9 - 3 = 7, u₄ = 3·7 - 3 = 1, u₅ = 3·1 - 9 = 11, u₆ = 3·11 - 7 = 9, u₇ = 3·9 - 1 = 9, u₈ = 3·9 - 11 = -1, u₉ = -3·1 - 9 = 5, u₁₀ =3·5 - 9 = 6, u₁₁ = 3·6 + 1 = 2, u₁₂ = 3·2 - 5 = 1, u₁₃ = 3·1 - 6 = -3, u₁₄ = -3·3 - 2 = 6, u₁₅ = 3·6 - 1 = 0, u₁₆ = 3·0 + 3 = 3, u₁₇ = 3·3 - 6 = 3, u₁₈ = 3·3 - 0 = 9. Hence u_n = u_n+16 mod 17 for n = 0, 1, 2. So the recurrence relation implies that u_n = u_n+16 mod 17 for all n, and hence that u_n = u_m mod 17 if n = m mod 16. Hence, in particular, u₁₇₈₈ = u₁₂ = 1 mod 17, and u₁₉₈₈ = u₄ = 1 mod 17. Hence [c¹⁷⁸⁸] and [c¹⁹⁸⁸] are divisible by 17.

Problem 8

u₁, u₂, ... , u_n are vectors in the plane, each with length at most 1, and with sum zero. Show that one can rearrange them as v₁, v₂, ... , v_n so that all the partial sums v₁, v₁ + v₂, v₁ + v₂ + v₃, ... , v₁ + v₂ + ... + v_n have length at most √5.

Solution

Suppose first that all the vectors are multiples of the unit vector e, so u_i = x_ie. We show that a stronger result holds with 1 in place of √5. List the positive x_i and some or all of the zero x_i in any order: s₁, s₂, s₃, ... . List the negative x_i and some or all of the zero x_i in any order: t₁, t₂, t₃, ... . Take s₁, then take the smallest i such that s₁ + t₁ + t₂ + ... t_i <= 0. Then take the smallest j such that s₁ + t₁ + t₂ + ... + t_i + s₂ + s₃ + ... + s_j ≥ 0 and so on. Clearly the partial sums all have absolute value at most max |x_i| ≤ 1.

Now take the subset of the vectors whose sum has the largest absolute value. Without loss of generality it is s = u₁, u₂, ... , u_m. Let the unit vector in the direction of s, and let the unit vector perpendicular to s be f. We may take the vectors u_i for i = 1, 2, ... , m to be x_ie + y_if and the remaining vectors to be X_je + Y_jf for j = 1, 2, ... , n-m. Since the vectors have zero sum we have y₁ + ... + y_m + Y₁ + ... + Y_n-m = 0. Also y₁ + ... + y_m = 0 and hence Y₁ + ... + Y_n-m = 0. By the maximality of s we have all x_i ≥ 0 and all X_i ≤ 0.

Using the first result, we may assume that all the partial sums |y₁ + y₂ + ... + y_i| ≤ 1 and |Y₁ + Y₂ + ... + Y_j| ≤ 1. Using the same technique as in the first result we may take blocks of terms alternately from x_i and X_j so that all the partial sums |x₁ + X₁ + ... + X_a + x₂ + ... + x_b + X_a+1 + ... | ≤ 1. The corresponding partial sums for the other coordinate are the sum of a partial sum of y_i and a partial sum of Y_j, so they each have absolute value at most 1 + 1 = 2. Hence the partial sums of the vectors all have absolute value at most √(1² + 2²) = √5. 

Problem 10

Let X = {1, 2, ... , n}. Find the smallest number of subsets f(n) of X with union X such that given any distinct a, b in X, one of the subsets contains just one of a, b.

Answer

If 2^k-1 ≤ n < 2^k, then f(n) = k.

Solution

Take k so that 2^k-1 ≤ n < 2^k. Then, adding leading zeros as necessary, we can write n as a k digit binary number. Let A_i be the numbers in X which (when written in binary) have a 1 in place i. That gives us a collection of k subsets. Any number in X must have at least one 1, so the A_i have union X. Any two distinct numbers in X must differ in at least one place, so if we take that place to be i, then A_i contains just one of the numbers. Thus f(n) ≤ k.

Now suppose we have a collection of h subsets which satisfies the condition. We can classify the elements according to whether they are in or out of A_i. That gives 2_h - 1 possible classifications (-1 because an element must be in at least one A_i) and no two elements can have the same classification. Hence n ≤ 2^h - 1. So 2^k-1 <= 2^h - 1 and hence k ≤ h, so k ≤ f(n).

Problem 12

ABC is a triangle. K, L, M are points on the sides BC, CA, AB respectively. D, E, F are points on the sides LM, MK, KL respectively. Show that (area AME)(area CKE)(area BKF)(area ALF)(area BDM)(area CLD) ≤ (1/8 area ABC)⁶.

Solution

area AME/area ABC = (area AME/area AMK) (area AMK/area ABK) (area ABK/area ABC) = (ME/MK) (AM/AB) (BK/BC). So, by the AM/GM inequality, we have (area AME/area ABC)^1/3 ≤ (1/3) (ME/MK + AM/AB + BK/BC).

Similarly, area CKE/area ABC = (area CKE/area CKM) (area CKM/area CBM) (area CBM/area CBA) = (KE/MK) (KC/BC) (MB/AB), and hence (area CKE/area ABC)^1/3 ≤ (1/3) (KE/MK + MB/AB + KC/BC).

Adding, we get (area AME)^1/3 + (area CKE)^1/3 ≤ (area ABC)^1/3. Similarly for the other pairs. So if we denote the areas of the 6 small triangles as A_i, we have ∑ A_i^1/3 ≤ 3 (area ABC)^1/3. Now applying AM/GM again we get ∑ A_i^1/3 ≥ 6 (∏ A_i^1/3)^1/6. So (area ABC)^1/3 ≤ 2 (∏ A_i^1/3)^1/6. Cubing gives: (∏ A_i)^1/6 <= (1/8) area ABC.

Problem 14

For what values of n, does there exist an n x n array of entries 0, ±1 such that all rows and columns have different sums?

Answer n even.

Solution

For n = 2m we may take:

1    1    1    1    1    1
-1    1    1    1    1    1
-1   -1    1    1    1    1
-1   -1   -1    0    1    1
-1   -1   -1   -1    0    1
-1   -1   -1   -1   -1    0

Thus rows 1, 2, ... , m have sums 2m, 2m-2, 2m-4, ... , 2, and the rows m+1, m+2, ... , 2m have sums -1, -3, ... , -(2m-1). Columns 1, 2, ... , m have sums -(2m-2), -(2m-4), ... , 0, and columns m+1, ... , 2m have sums 1, 3, 5, ... , 2m-1. So we get each of the sums -(2m-1), -(2m-2), ... , -1, 0, 1, 2, ... , 2m just once.

Now suppose that we have a solution a_ij for n. Let the row sums be r_i and the column sums be c_j. The r_i and c_j are all different and all lie in the range -n to n. There are 2n+1 values in that range. Let the value in the range -n to n not taken by any row or column sum be N.

Suppose that N = 0. Suppose there are k positive row sums. Then there are n-k negative row sums, n-k positive column sums and k negative column sums.

Suppose N > 0. Then n of the sums are negative and n are non-negative. So if there are k non-negative row sums, then there are n-k negative row sums, n-k non-negative column sums and k negative column sums.

Similarly, if N < 0, then n of the sums are positive and n are non-positive. So if there are k positive row sums, then there are n-k non-positive row sums, n-k positive column sums and k non-positive column sums.

Thus whatever the value of N, we may assume that there are k row sums ≥ 0, n-k row sums ≤ 0, n-k column sums ≥ 0, and k column sums ≤ 0. Let L be the set of row indices for which the row sum is ≥ 0, and R the set for which it is ≤ 0. Similarly, let L' be the set of column indices for which the column sum is ≥ 0, and R' the set for which it is ≤ 0.

Then we have ∑ |r_i| + ∑ |c_j| = ∑_L r_i - ∑_R r_i + ∑_L' c_j - ∑_R' c_j = ∑_LL' + ∑_LR' - ∑_RL' - ∑_RR' + ∑_LL' + ∑_RL' - ∑_LR' - ∑_RR', where ∑_LL' denotes the sum of a_ij for i in L and j in L' (and similarly for the other terms) = 2 ∑_LL' - 2 ∑_RR'. But ∑_LL' and ∑_RR' each have k(n-k) terms, each of which is at most 1, so 2 ∑_LL' - 2 ∑_RR' ≤ 4k(n-k). Hence ∑ |r_i| + ∑ |c_j| ≤ 4k(n-k). But ∑ |r_i| + ∑ |c_j| = 2(1 + 2 + ... + n) - |N| = n(n+1) - |N| ≥ n², so n² <= 4k(n-k). But n² - 4k(n-k) = (n - 2k)², so if n is odd then n² > 4k(n - k). Contradiction. 

Problem 15

ABC is an acute-angled triangle. H is the foot of the perpendicular from A to BC. M and N are the feet of the perpendiculars from H to AB and AC. L_A is the line through A perpendicular to MN. L_B and L_C are defined similarly. Show that L_A, L_B and L_C are concurrent.

Solution

Let O be the circumcenter. It is sufficient to show that O lies on L_A.

Angle AOB = 2 angle ACB. Hence angle BAO = 90^o - C.

Angles AMH and ANH are both 90^o, so AMHN is cyclic. Hence angle AMN = angle AHN = 90^o - angle HAN = C. Hence the angle between L_A and AB is 90^o - C. Hence O lies on L_A.

Problem 17

ABCDE is a convex pentagon such that BC, CD and DE are equal and each diagonal is parallel to a side (AC is parallel to DE, BD is parallel to AE etc). Show that the pentagon is regular.

Solution

Angle BEC = angle ECD (BE parallel to CD) = angle CED (DE = DC) = angle ACE (AC parallel to DE) = angle BAC (AB parallel to CE). So BAEC is cyclic, but BA is parallel to CE. Hence BC = AE. Similarly, AB = DE, so all the sides are equal.

Since BAEC is an isosceles trapezium, angle BAE = angle CBA. Similarly, all the other pairs of adjacent angles are equal, so all five angles are equal. Hence the pentagon is regular.

Problem 19

f has positive integer values and is defined on the positive integers. It satisfies f( f(m) + f(n) ) = m + n for all m, n. Find all possible values for f(1988).

Answer

1988.

Solution

f is obviously surjective. If f(a) = f(b), then c + a = f( f(c) + f(a) ) = f( f(c) + f(b) ) = c + b, so a = b. Hence f is injective. So the inverse f^-1 exists. The functional equation gives immediately f(m + n) = f^-1(m) + f^-1(n) and f^-1(m + n) = f(m) + f(n).

f(2n) = f^-1(2n-1) + f^-1(1) = f(2n-2) + f(1) + f^-1(1). Iterating, f(2n) = n f(1) + n f^-1(1). Similarly, f(2n+1) = n f(1) + (n+1) f^-1(1).

So we putting f(1) = h, f^-1(1) = k, we have f(1) = h, f(2) = h + k, f(3) = h + 2k, f(4) = 2h + 2k, f(5) = 2h + 3k, ... . But h, k ≥ 1 and f is surjective, so we must have h = k = 1. Hence f(n) = n for all n.

 

Problem 20

Find the smallest n such that if {1, 2, ... , n} is divided into two disjoint subsets then we can always find three distinct numbers a, b, c in the same subset with ab = c.

Answer

96.

Solution

We show first that however we partition {1, 2, 3, ... , 96}, one part always contains three distinct numbers a, b, c with ab = c. Suppose that we have a partition A, B with neither A nor B containing such a, b, c. We will obtain a contradiction. Without loss of generality 2 belongs to A.

Case 1 3 and 4 belong to A. Then 2.3 = 6, 2.4 = 8, and 3.4 = 12 belong to B. Hence 6.8 = 48, and 6.12 = 96 belong to A. Contradiction (2.48 = 96).

Case 2 3 belongs to A, 4 belongs to B. Then 2.3 = 6 belongs to B, 4.6 = 24 belongs to A. So 12 = 24/2 belongs to B. So 4.12 = 48 belongs to A. Contradiction (2.24 = 48).

Case 3 4 belongs to A, 3 belongs to B. Then 2.4 = 8 belongs to B, 3.8 = 24 belongs to A. So 24/2 = 12 and 24/4 = 6 belong to B. Hence 3.6 = 18 and 3.12 = 36 belong to A. Contradiction (2.18 = 36).

Case 4 3, 4 belong to B. Then 3.4 = 12 belongs to A. So 12/2 = 6 belongs to B. Hence 4.6 = 24 belongs to A. Contradiction (2.12 = 24).

Next we show that there is a partition of (1, 2, 3, ... , 95} such that neither part contains such a, b, c. Take

A pa for p prime and a = 1 or 2
 p4q, p3q2 for distinct primes p, q
 p2qr for distinct primes p, q, r
B pa for p prime and a = 3, 4, 5 or 6
 pq, p2q, p2q2, p3q for distinct primes p, q
 pqr for distinct primes p, q, r

Note that 2⁷ = 128 > 95, 2⁵3 = 96 > 95, so we do not need to consider p^a for a > 6 or p^aq for a > 4. Also 2³3³ = 216, so we do not need to consider p³q³. Finally 2²3²5 = 180, 2³3.5 = 120, so we do not need to consider any p^aq^br^c except pqr and p²qr. It is easy to check that A and B satisfy the condition. [Note that it does not extend to 96 because 2⁵3 = 2(2⁴3) = 2⁴(2.3).]

Finally for n < 95, A ⊆ {1, 2, ... , n} and B ⊆ {1, 2, ... , n} provide a partition of {1, 2, ... , n} with neither art containing such a, b, c.

Problem 21

49 students solve a set of 3 problems. Each problem is marked from 0 to 7. Show that there are two students A and B such that A scores at least as many as B for each problem.

Solution

We denote a set of scores by (a, b, c), where a is the score on the first problem, b the score on the second problem, and c the score on the third problem. Let X_i be set of (a, b, c) with a + b + c = i. Obviously we cannot have two distinct triples (a, b, c) and (a', b', c') both in X_i with a ≥ a', b ≥ b' and c ≥ c'. But it is easy to check that X₁₀ has 48 elements. So the result is false for 48 students (because each could have a different triple in X₁₀).

*** incomplete ***

Problem 22

Show that there are only two values of N for which (4N+1)(x₁² + x₂² + ... + x_N²)= 4(x₁ + x₂ + ... + x_N)² + 4N + 1 has an integer solution x_i.

Answer

N = 2 has the solution 9(1² + 2²) = 4(1 + 2)² + 9.
N = 6 has the solution 25(1² + 1² + 1² + 1² + 1² + 0²) = 4(1 + 1 + 1 + 1 + 1 + 0)² + 25.

Solution

Suppose every x_i is 0 or 1. Suppose there are M 1s. Then we have (4N+1)M = 4M² + 4N+1, so (4N+1)(M-1) = 4M². Since 4N+1 is odd, 4 must divide M-1. So M is odd. So 8 does not divide M-1. Since M-1 and M are coprime, no prime p > 2 can divide M-1. Hence M = 5. So N = 6. That is a possible solution (as shown explicitly above).

If x_i is a solution, then -x_i is also a solution. So let us assume that ∑ x_i ≥ 0. If some x_i is not 0 or 1, then either some x_i is negative, or some x_i > 1. In either case we have x_i² > x_i, so ∑ x_i < ∑ x_i². Put X = ∑ x_i. Then X + 1 ≤ ∑ x_i² = (4/(4N+1) X² + 1, so X ≥ (4N+1)/4 and hence X ≥ N+1.

By Cauchy, we have X² ≤ N ∑ x_i² = (4N/(4N+1) X² + N, so X² ≤ N(4N+1), so X ≤ 2N. Hence 1 < X/N ≤ 2.

We have ∑ (x_i - X/N)² = (∑ x_i²) - X²/N = 1 - X²/(N(4N+1)) < 1. Hence each |x_i - X/N| < 1. Hence 0 < x_i < 3. But x_i is an integer, so it must be 1 or 2. Suppose there are M 1s. Then there are N-M 2s and we have: 4MN - 3M - 4M² - 1 = 0. Hence M divides 1, so M = 1. Hence N = 2, and we have the other solution shown above. 

Problem 31

An even number of people have a discussion sitting at a circular table. After a break they sit down again in a different order. Show that there must be two people with the same number of people sitting between them before and after the break.

Solution

Label the people 0, 1, 2, ... , 2n-1. Suppose that before the break they are in the order 0, 1, 2, ... , 2n-1 (with 2n-1 also next to 0). Without loss of generality, we may assume that 0 sits in the same position after the break (rotating the table does not affect things). Suppose that after the break person i is in the position occupied by a_i before the break. Suppose the result is false. Then we must have a_i ≠ i for all i > 0 (otherwise 0 and i would have the same number of people between them before and after the break).

Suppose first that a_i - a_j ≠ i - j mod 2n for all unequal i, j. Then a_i - i ≠ a_j - j for i and j distinct. Hence, working mod 2n, a₁ - 1, a₂ - 2, ... , a_2n-1 - (2n-1) is just a permutation of 1, 2, ... , 2n-1. Hence ∑ (a_i - i) = ∑ i = n(2n - 1) = n mod 2n. But ∑ (a_i - i) = (∑ a_i) - (∑ i) = 0 mod 2n. Contradiction. So for some i > j we must have a_i - a_j = i - j. But 1 ≤ a_i, a_j ≤ 2n-1, so -(2n-2) < (a_i - a_j) ≤ 2n-2. So either a_i - a_j = i - j, or a_i - a_j = i - j - 2n. But the number of people between positions i and j is i - j - 1 going one way round and 2n - (i - j) - 1 going the other way round. So in either case there are the same number of people between persons i and j before and after the break. Contradiction.

  

International Mathematical Olympiad Volume 1: 1959-1975 (Anthem Learning)

International Mathematical Olympiad 1959 - 1999

USA And International Mathematical Olympiads 2005: Examples-pictures-proofs (Problem Books)

International Mathematical Olympiads 1959-1977 (New Mathematical Library)

USA & International Mathematical Olympiads 2003

50th IMO - 50 Years of International Mathematical Olympiads

USA and International Mathematical Olympiads 2001

International Mathematical Olympiad Volume 2: 1976-1990 (Anthem Learning)

USA & International Mathematical Olympiads 2002

Read more »

Posted in: IMO shortlist