42nd International Mathematical Olympiad 2001 Problems & Solutions

A1. ABC is acute-angled. O is its circumcenter. X is the foot of the perpendicular from A to BC. Angle C ≥ angle B + 30^o. Prove that angle A + angle COX < 90^o.

A2. a, b, c are positive reals. Let a' = √(a² + 8bc), b' = √(b² + 8ca), c' = √(c² + 8ab). Prove that a/a' + b/b' + c/c' ≥ 1.

A3. Integers are placed in each of the 441 cells of a 21 x 21 array. Each row and each column has at most 6 different integers in it. Prove that some integer is in at least 3 rows and at least 3 columns.

B1. Let n₁, n₂, ... , n_m be integers where m is odd. Let x = (x₁, ... , x_m) denote a permutation of the integers 1, 2, ... , m. Let f(x) = x₁n₁ + x₂n₂ + ... + x_mn_m. Show that for some distinct permutations a, b the difference f(a) - f(b) is a multiple of m!.

B2. ABC is a triangle. X lies on BC and AX bisects angle A. Y lies on CA and BY bisects angle B. Angle A is 60^o. AB + BX = AY + YB. Find all possible values for angle B.

B3. K > L > M > N are positive integers such that KM + LN = (K + L - M + N)(-K + L + M + N). Prove that KL + MN is composite.

Solutions

Problem A1

ABC is acute-angled. O is its circumcenter. X is the foot of the perpendicular from A to BC. Angle C ≥ angle B + 30^o. Prove that angle A + angle COX < 90^o

Solution

Take D on the circumcircle with AD parallel to BC. Angle CBD = angle BCA, so angle ABD ≥ 30^o. Hence angle AOD ≥ 60^o. Let Z be the midpoint of AD and Y the midpoint of BC. Then AZ ≥ R/2, where R is the radius of the circumcircle. But AZ = YX (since AZYX is a rectangle).

Now O cannot coincide with Y (otherwise angle A would be 90^o and the triangle would not be acute-angled). So OX > YX ≥ R/2. But XC = YC - YX < R - YX ≤ R/2. So OX > XC.

Hence angle COX < angle OCX. Let CE be a diameter of the circle, so that angle OCX = angle ECB. But angle ECB = angle EAB and angle EAB + angle BAC = angle EAC = 90^o, since EC is a diameter. Hence angle COX + angle BAC < 90^o.

Problem A2

a, b, c are positive reals. Let a' = √(a² + 8bc), b' = √(b² + 8ca), c' = √(c² + 8ab). Prove that a/a' + b/b' + c/c' >= 1.

Solution

A not particularly elegant, but fairly easy, solution is to use Cauchy: (∑ xy)² ≤ ∑ x² ∑ y².

To get the inequality the right way around we need to take x² = a/a' [to be precise, we are taking x₁² = a/a', x₂² = b/b', x₃² = c/c'.]. Take y² = a a', so that xy = a. Then we get ∑ a/a' >= (∑ a)²/∑ a a'.

Evidently we need to apply Cauchy again to deal with ∑ a a'. This time we want ∑ a a' ≤ something. The obvious X=a, Y=a' does not work, but if we put X=a^1/2, Y=a^1/2a', then we have ∑ a a' ≤ (∑ a)^1/2 (∑ a a'²)^1/2. So we get the required inequality provided that (∑ a)^3/2 ≥ (∑ a a'²)^1/2 or (∑ a)³ ≥ ∑ a a'².

Multiplying out, this is equivalent to: 3(ab² + ac² + ba² + bc² + ca² + cb²) ≥ 18abc, or a(b - c)² + b(c - a)² + c(a - b)² ≥ 0, which is clearly true.

Problem A3

Integers are placed in each of the 441 cells of a 21 x 21 array. Each row and each column has at most 6 different integers in it. Prove that some integer is in at least 3 rows and at least 3 columns.

Solution

Notice first that the result is not true for a 20 x 20 array. Make 20 rectangles each 2 x 10, labelled 1, 2, ... , 20. Divide the 20 x 20 array into four quadrants (each 10 x 10). In each of the top left and bottom right quadrants, place 5 rectangles horizontally. In each of the other two quadrants, place 5 rectangles vertically. Now each row intersects 5 vertical rectangles and 1 horizontal. In other words, it contains just 6 different numbers. Similarly each column. But any given number is in either 10 rows and 2 columns or vice versa, so no number is in 3 rows and 3 columns. [None of this is necessary for the solution, but it helps to show what is going on.]

Returning to the 21 x 21 array, assume that an arrangement is possible with no integer in at least 3 rows and at least 3 columns. Color a cell white if its integer appears in 3 or more rows and black if its integer appears in only 1 or 2 rows. We count the white and black squares.

Each row has 21 cells and at most 6 different integers. 6 x 2 < 21, so every row includes an integer which appears 3 or more times and hence in at most 2 rows. Thus at most 5 different integers in the row appear in 3 or more rows. Each such integer can appear at most 2 times in the row, so there are at most 5 x 2 = 10 white cells in the row. This is true for every row, so there are at most 210 white cells in total.

Similarly, any given column has at most 6 different integers and hence at least one appears 3 or more times. So at most 5 different integers appear in 2 rows or less. Each such integer can occupy at most 2 cells in the column, so there are at most 5 x 2 = 10 black cells in the column. This is true for every column, so there are at most 210 black cells in total.

This gives a contradiction since 210 + 210 < 441.

Comment. This looks easy, but (like question 6) I found it curiously difficult (it took me well over 2 hours). For a while I could not see how to do better than a 12 x 12 array (with 2 rows of 1s, then 2 rows of 2s etc), which was disorienting. Then I got the argument almost right, but not quite right, which took more time.

The original question was phrased in terms of 21 boys and 21 girls in a competition with an unknown number of problems. Each boy, girl pair solved at least one problem. Each competitor solved at most 6 problems. One had to show that some problem was solved by at least 3 boys and at least 3 girls. The recasting in the terms above is almost immediate.

Equally, one can easily recast the solution above into the competition format. Take any boy B₀. At least one of the questions he attempts must be attempted by 3 or more girls (because he attempts at most 6 questions and there are more than 6x2 girls). Hence he attempts at most 5 questions which are only attempted by less than 3 girls. So at most 5 x 2 = 10 of the 21 pairs (B₀, G) attempt a question attempted by less than 3 girls. So at most 210 of the 441 pairs pairs (B, G) attempt such a question. Similarly, at most 210 pairs (B, G) attempt a question attempted by less than 3 boys. Hence at least 21 pairs (B, G) attempt a question attempted by 3 or more girls and 3 or more boys. So there must be at least one such question.

Note that the arguments above generalise immediately to show that in a 4N+1 by 4N+1 array with at most N+1 different integers in each row and column, there is some integer that appears in at least 3 rows and 3 columns, but this is not true for a 4N by 4N array.

Problem B1

Let n₁, n₂, ... , n_m be integers, where m is odd. Let x = (x₁, ... , x_m) denote a permutation of the integers 1, 2, ... , m. Let f(x) = x₁n₁ + x₂n₂ + ... + x_mn_m. Show that for some distinct permutations a, b the difference f(a) - f(b) is a multiple of m!.

Solution

This is a simple application of the pigeon hole principle.

The sum of all m! distinct residues mod m! is not divisible by m! because m! is even (since m > 1). [The residues come in pairs a and m! - a, except for m!/2.].

However, the sum of all f(x) as x ranges over all m! permutations is 1/2 (m+1)! ∑ n_i, which is divisible by m! (since m+1 is even). So at least one residue must occur more than once among the f(x).

Problem B2

ABC is a triangle. X lies on BC and AX bisects angle A. Y lies on CA and BY bisects angle B. Angle A is 60^o. AB + BX = AY + YB. Find all possible values for angle B.

Answer

Answer: 80^o.

Solution

This is an inelegant solution, but I did get it fast! Without loss of generality we can take length AB = 1. Take angle ABY = x. Note that we can now solve the two triangles AXB and AYB. In particular, using the sine rule, BX = sin 30^o/sin(150^o-2x), AY = sin x/sin(120^o-x), YB = sin 60^o/sin(120^o-x). So we have an equation for x.

Using the usual formula for sin(a + b) etc, and writing s = sin x, c = cos x, we get: 2√3 s²c - 4sc - 2√3 c³ + 2√3 c² + 6sc - 2s - √3 = 0 or -√3 (4c³ - 2c² - 2c + 1) = 2s(2c² -3c + 1). This has a common factor 2c - 1. So c = 1/2 or -√3 (2c² - 1) = 2s(c - 1) (*).

c = 1/2 means x = 60^o or angle B = 120^o. But in that case the sides opposite A and B are parallel and the triangle is degenerate (a case we assume is disallowed). So squaring (*) and using s² = 1 - c², we get: 16c⁴ - 8c³ - 12c² + 8c - 1 = 0. This has another factor 2c - 1. Dividing that out we get: 8c³ - 6c + 1 = 0. But we remember that 4c³ - 3c = cos 3x, so we conclude that cos 3x = -1/2. That gives x = 40^o, 80^o, 160^o, 200^o, 280^o, 320^o. But we require that x < 60^o to avoid degeneracy. Hence the angle B = 2x = 80^o.

I subsequently found this geometric solution on the official Wolfram site (Wolfram was one of the sponsors of IMO 2001). I cannot say it is much easier, but at least it is geometric.

Extend AB to X' with BX' = BX. Extend AY to Z with YZ = YB. Then AZ = AY + YZ = AY + YB = AB + BX = AB + BX' = AX'. Angle A = 60^o, so AZX' is equilateral.

Use B also to denote the angle at B. Then angle YBX = B/2. Also angle BXX' + angle BX'X = B. The triangle is isosceles by construction, so angle BX'X = B/2. Hence angle XX'Z = 60^o - B/2. X lies on the bisector of A and AZ = AX', so XZ = XX'. Hence XZX' = 60^o - B/2 also. But angle Z = 60^o, so angle YZX = B/2 = angle YBX.

Now YZ = YB, so angle YZB = angle YBZ. Hence angle XZB = angle XBX (they are the difference of pairs of equal angles). If X does not lie on BZ, then we can conclude that XB = XZ.

In that case, since XZ = XX', we have XB = XX'. But already XB = BX' (by construction), so BXX' is equilateral and hence B/2 = 60^o. But then angle B + angle A = 180^o, so the triangle ABC is degenerate (with C at infinity), which we assume is disallowed. Hence X must lie on BZ, which means Z = C and angle B = 2 angle C. Hence angle B = 80, angle C = 40.

Problem B3

K > L > M > N are positive integers such that KM + LN = (K + L - M + N)(-K + L + M + N). Prove that KL + MN is composite.

Solution

Note first that KL+MN > KM+LN > KN+LM, because (KL+MN) - (KM+LN) = (K - N)(L - M) > 0 and (KM+LN) - (KN+LM) = (K - L)(M - N) > 0.

Multiplying out and rearranging, the relation in the question gives K² - KM + M² = L² + LN + N². Hence (KM + LN)(L² + LN + N²) = KM(L² + LN + N²) + LN(K² - KM + M²) = KML² + KMN² + K²LN + LM²N = (KL + MN)(KN + LM). In other words (KM + LN) divides (KL + MN)(KN + LM).

Now suppose KL + MN is prime. Since it greater than KM + LN, it can have no common factors with KM + LN. Hence KM + LN must divide the smaller integer KN + LM. Contradiction.

Comment. This looks easy, but in fact I found it curiously difficult. It is easy to go around in circles getting nowhere. Either I am getting older, or this is harder than it looks!

Note that it is not hard to find K, L, M, N satisfying the condition in the question. For example 11, 9, 5, 1.

OLYMPIAD 1995. OLYMPIC HIGH SCHOOL. OLYMPIA, WASHINGTON STATE. YEARBOOK. ANNUAL.