29th IMO 1988 shortlist

29th IMO 1988 shortlisted problems


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.