Shortlisted Problems for the 29th IMO

Canberra (Australia), 1988

Original HTML-version by Enrique Valeriano Cuba

Problem 1. (BUL 1)
An integer sequence is defined by

an = 2an-1 + an-2, (n>1), a0 = 0, a1 = 1.

Prove that 2k divides an if and only if 2k divides n.

Problem 2. (BUL 3)
Let n be a positive integer. Find the number of odd coefficients of the polynomial

un (x) = (x2 + x + 1)n.

Problem 3. (CAN 1)
The triangle ABC is inscribed in a circle. The interior bisectors of the angles A, B and C meet the circle again at A', B' and C', respectively. Prove that the area of triangle A'B'C' is greater than or equal to the area of triangle ABC.

Problem 4. (CZE 1)
An n x n chessboard (n ³ 2) is numbered by the numbers 1, 2, ..., n2 (and every number occurs). Prove that there exist two neighbouring (with common edge) squares such that their numbers differ by at least n.

Problem 5. (CZE 2)
Let n be an even positive integer. Let A1, A2, ..., An+1 be sets having n elements each such that any two of them have exactly one element in common while every element of their union belongs to at least two of the given sets. For which n can one assign to every element of the union one of the numbers 0 and 1 in such a manner that each of the sets has exactly n/2 zeros?.

Problem 6. (CZE 3)
In a given tetrahedron ABCD let K and L be the centres of edges AB and CD, respectively. Prove that every plane that contains the line KL divides the tetrahedron into two parts of equal volume.

Problem 7. (FRA 2)
Let a the greatest positive root of the equation x3 - 3x2 + 1 = 0. Show that [a1788] and [a1988] are both divisible by 17. ( [x] denotes the integer part of x).

Problem 8. (FRA 3)
Let u1, u2, ..., um be m vectors in the plane, each of length £ 1, with zero sum. Show that one can rearrange u1, u2, ..., um as a sequence v1, v2, ..., vm such that each partial sum v1, v1 + v2, v1 + v2 + v3, ..., v1 + v2 + ... + vm has length less than or equal to Ö5.

Problem 9. (FRG 1)
Let a and b be two positive integers such that ab + 1 divides a2 + b2. Show that (a2 + b2)/(ab + 1) is a perfect square.

Problem 10. (GDR 1)
Let N = {1, 2, ..., n}, n ³ 2. A collection F = {A1, ..., At} of subsets Ai Í N, i = 1, ..., t, is said to be separating, if for every pair {x,y} Í N, there is a set Ai Î F so that Ai Ç {x,y} contains just one element. F is said to be covering, if every element of N is contained in at least one set Ai Î F. What is the smallest value f(n) of t, so that there is a set F = {A1, ..., At} which is simultaneously separating and covering.

Problem 11. (GDR 3)
The lock on a safe consist of 3 wheels, each of which may be set in 8 different positions. Due to a defect in the safe mechanism the door will open if any two of the three wheels are in the correct position. What is the smallest number of combinations which must be tried if one is to guarantee being able to open the safe (assumming the "right combination" is not known)?.

Problem 12. (GRE 2)
In a triangle ABC, choose any points K Î BC, L Î AC, M Î AB, N Î LM, R Î MK and F Î KL. If E1, E2, E3, E4, E5, E6 and E denotes the areas of the triangles AMR, CKR, BKF, ALF, BNM, CLN and ABC, respectively. Show that

E ³ 8(E1E2E 3E4E5E6)1/6.

Problem 13. (GRE 3)
In a right-angled triangle ABC let AD be the altitude drawn to the hypotenuse and let the straight line joining the incentres of the triangles ABD, ACD intersect the sides AB, AC at the points K, L respectively. If E and E1 denote the areas of the triangles ABC and AKL respectively, show that E/E1 ³ 2.

Problem 14. (HUN 1)
For what values of n does there exist an n x n array of entries -1, 0 or 1 such that the 2n sums obtaines by summing the elements of the rows and the columns are all different?.

Problem 15. (ICE 1)
Let ABC be an acute-angled triangle. Three lines LA , LB and LC are constructed through the vertices A, B and C, respectively according to the following description: Let H be the foot of the altitude drawn from the vertex A to the side BC; let SA be the circle with diameter AH; let SA meet the sides AB and AC at M and N respectively, where M and N are distinct from A; then LA is the line through A perpendicular to MN. The lines LB and LC are constructed similarly. Prove that LA , LB and LC are concurrent.

Problem 16. (IRE 1)
Show that the solution set of the inequality

S k/(x-k) ³ 5/4; (the sum is takne from k = 1 to k = 70)

is a union of disjoint intervals, the sum of whose lengths is 1988.

Problem 17. (ISA 2)
In the convex pentagon ABCDE, the sides BC, CD, DE are equal. Moreover each diagonal is parallel to a side (AC is parallel to DE, BD is parallel to AE, etc.). Prove that ABCDE is a regular pentagon.

Problem 18. (LUX 1)
Consider 2 concentric circles of radii R and r (R > r) with centre O. Fix P on the small circle and consider the variable chord PA of the small circle. Points B and C lie on the large circle; B, P, C are collinear and BC is perpendicular to AP.

Problem 19. (MEX 1)
Let f(n) be a function defined on the set of all positive integers and having its values in the same set. Suppose that f ( f(n) + f(m) ) = m + n for all positive integers n,m. Find all possible values for f (1988).

Problem 20. (MON 4)
Find the least natural number n such that, if the set {1, 2, ..., n} is arbitrarily divided into two non-intersecting subsets, then one of the subsets contains 3 distinct numbers such that the product of two of them equals the third.

Problem 21. (POL 4)
Forty-nine students solve a set of 3 problems. The score for each problem is a whole number of points from 0 to 7. Prove that there exist two students A and B such that, for each problem, A will score at least as many points as B.

Problem 22. (ROK 2)
Let p be the product of two consecutive integers greater than 2. Show that there no integers x1, x2, ..., xp satisfying the equation

S (xi2) - (4/(4p+1)).(S xi) 2 = 1

or show there are only two values of p for which there are integers x1, x2, ..., xp satisfying

S (xi2) - (4/(4p+1)).(S xi) 2 = 1

where all the sums are taken from i = 1 to i = p.

Problem 23. (SIN 2)
Let Q be the centre of the inscribed circle of a triangle ABC. Prove that for any point P,

a(PA)2 + b(PB)2 + c(PC)2 = a(QA)2 + b(QB)2 + c(QC)2 + (a + b + c)(QP)2,

where a=BC, b=CA and c=AB.

Problem 24. (SWE 2)
Let {ak}1¥ be a sequence of non-negative real numbers such that

ak - 2ak+1 + ak+2 ³ 0 and S aj £ 1 for all k = 1, 2, ... ,

where the sum is taken from j=1 to j=k. Prove that

0 £ (ak - ak+1) < 2/(k2) for all k = 1, 2, ... .

Problem 25. (UNK 1)
A positive integer is called a double number if its decimal representation consists of a block of digits, not commencing with 0, followed immediately by an identical block. So, for instance, 360360 is a double number, but 36036 is not. Show that there are infinitely many double numbers which are perfect squares.

Problem 26. (UNK 2)
A function f defined on the positive integers (and taking positive integer values) is given by:

f(1) = 1, f(3) = 3,
f (2n) = f (n),
f (4n+1) = 2 f(2n+1) - f(n),
f (4n+3) = 3 f(2n+1) - 2f(n),
for all positive integers n. Determine with proof the number of positive integers £ 1988 for which f(n) = n.

Problem 27. (UNK 4)
The triangle ABC is acute-angled. L is any line in the plane of the triangle and u, v, w are the lengths of the perpendiculars from A, B, C respectively to L. Prove that

u2tan A + v2tan B + w2tan C ³ 2 D,

where D is the area of the triangle, and determine the lines L for which equality holds.

Problem 28. (UNK 5)
The sequence {an} of integers is defined by

a1 = 2, a2 = 7

-1/2 < an+1 - (an2)/ (an-1) £ 1/2; for n ³ 2.

Prove that an is odd for all n > 1.

Problem 29. (USA 3)
A number of signal lights are equally spaced along one-way railroad track, labeled in order 1, 2, ..., N (N ³ 2). As a safety rule, a train is not allowed to pass a signal if any other train is in motion on the length of track between it and the following signal. However, thers is no limit to the number of trains that can be parked motionless at a signal, one behind the other. (Assume the trains have zero length.)
A series of K freight trains must be driven from Signal 1 to Signal N. Each train travels at a distinct but constant speed at all times when it is not blocked by the safety rule. Show that, regardless of the order in which the trains are arranged, the same time will elapse between the first train's departure from Signal 1 and the last train's arrival at Signal N.

Problem 30. (USS 1)
A point M is chosen on the side AC of the triangle ABC in such a way that the radii of the circles inscribed in the triangles ABM and BMC are equal. Prove that

BM2 = D cot (B/2),

where D is the area of the triangle ABC.

Problem 31. (USS 2)
Around a circular table an even number of persons have a discussion. After break they sit again around the circular table in a different order. Prove that there are at least two people such that the number of participants sitting between them before and after the break is the same.