42nd IMO 2001 shortlisted problems

Algebra
A1.  Let T be the set of all triples (a, b, c) where a, b, c are non-negative integers. Find all real-valued functions f on T such that f(a, b, c) = 0 if any of a, b, c are zero and f(a, b, c) = 1 + 1/6 f(a+1, b-1, c) + 1/6 f(a-1, b+1, c) + 1/6 f(a+1, b, c-1) + 1/6 f(a-1, b, c+1) + 1/6 f(a, b+1, c-1) + 1/6 f(a, b-1, c+1) for a, b, c all positive.
A2.  Show that any infinite sequence an of positive numbers satisfies an > an-121/n - 1 for infinitely many n.
A3.  Show that x1/(1 + x12) + x2/(1 + x12 + x22) + ... + xn/(1 + x22 + ... + xn2) < √n for all real numbers xi.
A4.  Find all real-valued functions f on the reals such that f(xy) ( f(x) - f(y) ) = (x - y) f(x) f(y) for all x, y.
A5.  Find all positive integers a0 = 1, a1, a2, ... , an such that a0/a1 + a1/a2 + ... + an-1/an = 99/100 and (ak+1 - 1)ak-1 ≥ ak3 - ak2 for k = 1, 2, ... , n-1.
Combinatorics
C1.  What is the largest number of subsequences of the form n, n+1, n+2 that a sequence of 2001 positive integers can have? For example, the sequence 1, 2, 2, 3, 3, of 5 terms has 4 such subsequences.
C3.  A finite graph is such that there are no subsets of 5 points with all 15 edges and every two triangles have at least one point in common. Show that there are at most two points X such that removing X leaves no triangles.
C4.  Let P be the set of all sets of three integers of the form {n, n+1776, n + 3777} or {n, n+2001, n+3777}. Show that we can write the set {0, 1, 2, 3, ... } as a union of disjoint members of P.
C5.  Find all finite sequences a0, a1, a2, ... , an such that am equals the number of times that m appears in the sequence.
C6.  Show that there is a set P of (2n)!/(n! (n+1)!) sequences of 2n terms, half 1s and half 0s, such that any sequence of 2n terms, half 1s and half 0s, is either in P or can be derived from a member of P by moving one term. Moving a term means changing a1, a2, ... , a2n to a1, a2, ... , ai-1, ai+1, ... , ajaiaj+1 ... an for some i, j. For example, by moving the initial 0 we can change 0110 to 1010 or 1100, or by moving the first 1 we can change 0110 to 1010 or 0101.
C7.  There are n piles of stones in a line. If a pile contains at least two stones more than the pile on its right, then a stone can be moved to the pile on its right. Initially, all the piles are empty except the leftmost pile which has n stones. If more than one move is possible, then a possible move is chosen arbitrarily. Show that after a finite number of moves, no more moves are possible and that the final configuration is independent of the moves made. Describe the final configuration. For example, we n = 6, one might get successively: 5 1, 4 2, 4 1 1, 3 2 1.
Geometry
G1.  ABC is an acute-angled triangle. A' is the center of the square with two vertices on BC, one on AB and one on AC. Similarly, B' is the center of the square with two vertices on CA, one on AB and one on BC, and C' is the center of the square with two vertices on AB, one on BC and one on CA. Show that AA', BB' and CC' are concurrent.
G3.  ABC is a triangle with centroid G and side lengths a = BC, b = CA, c = AB. Find the point P in the plane which minimises AP.AG + BP.BG + CP.CG and find the minimum in terms of a, b, c.
G4.  P is a point inside the triangle ABC. The feet of the perpendiculars to the sides are D, E, F. Find the point P which maximises PD.PE.PF/(PA.PB.PC). Which triangles give the largest maximum value?
G5.  ABC is an acute-angled triangle. B' is a point on the perpendicular bisector of AC on the opposite side of AC to B such that angle AB'C = 2A. A' and C' are defined similarly (with angle CA'B = 2C, angle BC'A = 2B). The lines AA' and B'C' meet at A". The points B" and C" are defined similarly. Find AA'/A"A' + BB'/B"B' + CC'/C"C'.
G6.  P is a point outside the triangle ABC. The perpendiculars from P meet the lines BC, CA, AB at D, E, F, respectively. The triangles PAF, PBD, PCE all have equal area. Show that their area must equal that of ABC.
G7.  P is a point inside acute-angled the triangle ABC. The perpendiculars from P meet the sides BC, CA, AB at D, E, F, respectively. Show that P is the circumcenter iff each of the triangles AEF, BDF, CDE has perimeter not exceeding that of DEF.
Number theory
N1.  Prove that we cannot find consecutive factorials with first digits 1, 2, ... , 9.
N2.  Find the largest real k such that if a, b, c, d are positive integers such that a + b = c + d, 2ab = cd and a ≥ b, then a/b ≥ k.
N3.  The sequence an is defined by a1= 1111, a2 = 1212, a3 = 1313, and an+3 = |an+2 - an+1| + |an+1 - an|. Find an, where n = 1414.
N4.  Let p > 3 be a prime. Show that there is a positive integer n < p-1 such that np-1 - 1 and (n+1)p-1 - 1 are not divisible by p2.
N6.  Do there exist 100 positive integers not exceeding 25000 such that the sum of every pair is distinct?
Note: problems A6, C2, C8, G2, G8 and N5 were used in the Olympiad and are not shown here.

Shortlist home
 
© John Scholes
jscholes@kalva.demon.co.uk
6 Aug 2002
Last corrected 15 Oct 2002