41st International Mathematical Olympiad 2000 Problems & Solutions

A1.  AB is tangent to the circles CAMN and NMBD. M lies between C and D on the line CD, and CD is parallel to AB. The chords NA and CM meet at P; the chords NB and MD meet at Q. The rays CA and DB meet at E. Prove that PE = QE.

A2.  A, B, C are positive reals with product 1. Prove that (A - 1 + 1/B)(B - 1 + 1/C)(C - 1 + 1/A) ≤ 1.

A3.  k is a positive real. N is an integer greater than 1. N points are placed on a line, not all coincident. A move is carried out as follows. Pick any two points A and B which are not coincident. Suppose that A lies to the right of B. Replace B by another point B' to the right of A such that AB' = k BA. For what values of k can we move the points arbitarily far to the right by repeated moves?

B1.  100 cards are numbered 1 to 100 (each card different) and placed in 3 boxes (at least one card in each box). How many ways can this be done so that if two boxes are selected and a card is taken from each, then the knowledge of their sum alone is always sufficient to identify the third box?

B2.  Can we find N divisible by just 2000 different primes, so that N divides 2^N + 1? [N may be divisible by a prime power.]

B3.  A₁A₂A₃ is an acute-angled triangle. The foot of the altitude from A_i is K_i and the incircle touches the side opposite A_i at L_i. The line K₁K₂ is reflected in the line L₁L₂. Similarly, the line K₂K₃ is reflected in L₂L₃ and K₃K₁ is reflected in L₃L₁. Show that the three new lines form a triangle with vertices on the incircle.

Solutions

Problem A1

AB is tangent to the circles CAMN and NMBD. M lies between C and D on the line CD, and CD is parallel to AB. The chords NA and CM meet at P; the chords NB and MD meet at Q. The rays CA and DB meet at E. Prove that PE = QE.

Solution

Angle EBA = angle BDM (because CD is parallel to AB) = angle ABM (because AB is tangent at B). So AB bisects EBM. Similarly, BA bisects angle EAM. Hence E is the reflection of M in AB. So EM is perpendicular to AB and hence to CD. So it suffices to show that MP = MQ.

Let the ray NM meet AB at X. XA is a tangent so XA² = XM·XN. Similarly, XB is a tangent, so XB² = XM·XN. Hence XA = XB. But AB and PQ are parallel, so MP = MQ. 

Problem A2

A, B, C are positive reals with product 1. Prove that (A - 1 + 1/B)(B - 1 + 1/C)(C - 1 + 1/A) ≤ 1.

Solution

An elegant solution due to Robin Chapman is as follows:

(B - 1 + 1/C) = B(1 - 1/B + 1/(BC) ) = B(1 + A - 1/B). Hence, (A - 1 + 1/B)(B - 1 + 1/C) = B(A² - (1 - 1/B)²) ≤ B A². So the square of the product of all three ≤ B A² C B² A C² = 1.

Actually, that is not quite true. The last sentence would not follow if we had some negative left hand sides, because then we could not multiply the inequalities. But it is easy to deal separately with the case where (A - 1 + 1/B), (B - 1 + 1/C), (C - 1 + 1/A) are not all positive. If one of the three terms is negative, then the other two must be positive. For example, if A - 1 + 1/B < 0, then A < 1, so C - 1 + 1/A > 0, and B > 1, so B - 1 + 1/C > 0. But if one term is negative and two are positive, then their product is negative and hence less than 1.

Few people would manage this under exam conditions, but there are plenty of longer and easier to find solutions! 

Problem A3

k is a positive real. N is an integer greater than 1. N points are placed on a line, not all coincident. A move is carried out as follows. Pick any two points A and B which are not coincident. Suppose that A lies to the right of B. Replace B by another point B' to the right of A such that AB' = k BA. For what values of k can we move the points arbitrarily far to the right by repeated moves?

Answer

k ≥ 1/(N-1).

Solution

An elegant solution by Gerhard Woeginger is as follows:

Suppose k < 1/(N-1), so that k₀ = 1/k - (N - 1) > 0. Let X be the sum of the distances of the points from the rightmost point. If a move does not change the rightmost point, then it reduces X. If it moves the rightmost point a distance z to the right, then it reduces X by at least z/k - (N-1)z = k₀ z. X cannot be reduced below nil. So the total distance moved by the rightmost point is at most X₀/k₀, where X₀ is the initial value of X.

Conversely, suppose k ≥ 1/(N-1), so that k₁ = (N-1) - 1/k ≥ 0. We always move the leftmost point. This has the effect of moving the rightmost point z > 0 and increasing X by (N-1)z - z/k = k₁z ≥ 0. So X is never decreased. But z ≥ k X/(N-1) ≥ k X₀/(N-1) > 0. So we can move the rightmost point arbitrarily far to the right (and hence all the points, since another N-1 moves will move the other points to the right of the rightmost point). 

Problem B1

100 cards are numbered 1 to 100 (each card different) and placed in 3 boxes (at least one card in each box). How many ways can this be done so that if two boxes are selected and a card is taken from each, then the knowledge of their sum alone is always sufficient to identify the third box?

Answer

12. Place 1, 2, 3 in different boxes (6 possibilities) and then place n in the same box as its residue mod 3. Or place 1 and 100 in different boxes and 2 - 99 in the third box (6 possibilities).

Solution

An elegant solution communicated (in outline) by both Mohd Suhaimi Ramly and Fokko J van de Bult is as follows:

Let H_n be the corresponding result that for cards numbered 1 to n the only solutions are by residue mod 3, or 1 and n in separate boxes and 2 to n - 1 in the third box. It is easy to check that they are solutions. H_n is the assertion that there are no others. H₃ is obviously true (although the two cases coincide). We now use induction on n. So suppose that the result is true for n and consider the case n + 1.

Suppose n + 1 is alone in its box. If 1 is not also alone, then let N be the sum of the largest cards in each of the boxes not containing n + 1. Since n + 2 ≤ N ≤ n + (n - 1) = 2n - 1, we can achieve the same sum N as from a different pair of boxes as (n + 1) + (N - n - 1). Contradiction. So 1 must be alone and we have one of the solutions envisaged in H_n+1.

If n + 1 is not alone, then if we remove it, we must have a solution for n. But that solution cannot be the n, 1, 2 to n - 1 solution. For we can easily check that none of the three boxes will then accomodate n + 1. So it must be the mod 3 solution. We can easily check that in this case n + 1 must go in the box with matching residue, which makes the (n + 1) solution the other solution envisaged by H_n+1. That completes the induction.

My much more plodding solution (which I was quite pleased with until I saw the more elegant solution above) follows. It took about half-an-hour and shows the kind of kludge one is likely to come up with under time pressure in an exam!

With a suitable labeling of the boxes as A, B, C, there are 4 cases to consider:

Case 1: A contains 1; B contains 2; C contains 3
Case 2: A contains 1,2
Case 3: A contains 1, 3; B contains 2
Case 4: A contains 1; B contains 2, 3.

We show that Cases 1 and 4 each yield just one possible arrangement and Cases 2 and 3 none.

In Case 1, it is an easy induction that n must be placed in the same box as its residue (in other words numbers with residue 1 mod 3 go into A, numbers with residue 2 go into B, and numbers with residue 0 go into C). For (n + 1) + (n - 2) = n + (n - 1). Hence n + 1 must go in the same box as n - 2 (if they were in different boxes, then we would have two pairs from different pairs of boxes with the same sum). It is also clear that this is a possible arrangement. Given the sum of two numbers from different boxes, take its residue mod 3. A residue of 0 indicates that the third (unused) box was C, a residue of 1 indicates that the third box was A, and a residue of 2 indicates that the third box was B. Note that this unique arrangement gives 6 ways for the question, because there are 6 ways of arranging 1, 2 and 3 in the given boxes.

In Case 2, let n be the smallest number not in box A. Suppose it is in box B. Let m be the smallest number in the third box, C. m - 1 cannot be in C. If it is in A, then m + (n - 1) = (m - 1) + n. Contradiction (m is in C, n - 1 is in A, so that pair identifies B as the third box, but m - 1 is in A and n is in B, identifying C). So m - 1 must be in B. But (m - 1) + 2 = m + 1. Contradiction. So Case 2 is not possible.

In Case 3, let n be the smallest number in box C, so n - 1 must be in A or B. If n - 1 is in A, then (n - 1) + 2 = n + 2. Contradiction (a sum of numbers in A and B equals a sum from C and A). If n - 1 is in B, then (n - 1) + 3 = n + 2. Contradiction ( a sum from B and A equals a sum from C and B). So Case 3 is not possible.

In Case 4, let n be the smallest number in box C. n - 1 cannot be in A, or (n - 1) + 2 = 3 + n (pair from A, B with same sum as pair from B, C), so n - 1 must be in B. Now n + 1 cannot be in A (or (n + 1) + 2 = 3 + n), or in B or C (or 1 + (n + 1) = 2 + n). So n + 1 cannot exist and hence n = 100. It is now an easy induction that all of 4, 5, ... 98 must be in B. For given that m is in B, if m + 1 were in A, we would have 100 + m = 99 + (m + 1). But this arrangement (1 in A, 2 - 99 in B, 100 in C) is certainly possible: sums 3 - 100 identify C as the third box, sum 101 identifies B as the third box, and sums 102-199 identify A as the third box. Finally, as in Case 1, this unique arrangement corresponds to 6 ways of arranging the cards in the given boxes. 

Problem B2

Can we find N divisible by just 2000 different primes, so that N divides 2^N + 1? [N may be divisible by a prime power.]

Answer

Yes

Solution

Note that for b odd we have 2^ab + 1 = (2^a + 1)(2^a(b-1) - 2^a(b-2) + ... + 1), and so 2^a + 1 is a factor of 2^ab + 1. It is sufficient therefore to find m such that (1) m has only a few distinct prime factors, (2) 2^m + 1 has a large number of distinct prime factors, (3) m divides 2^m + 1. For then we can take k, a product of enough distinct primes dividing 2^m + 1 (but not m), so that km has exactly 2000 factors. Then km still divides 2^m + 1 and hence 2^km + 1.

The simplest case is where m has only one distinct prime factor p, in other words it is a power of p. But if p is a prime, then p divides 2^p - 2, so the only p for which p divides 2^p + 1 is 3. So the questions are whether a_h = 2^m + 1 is (1) divisible by m = 3^h and (2) has a large number of distinct prime factors.

a_h+1 = a_h(2^2m - 2^m + 1), where m = 3^h. But 2^m = (a_h - 1), so a_h+1 = a_h(a_h² - 3 a_h + 3). Now a₁ = 9, so an easy induction shows that 3^h+1 divides a_h, which answers (1) affirmatively. Also, since a_h is a factor of a_h+1, any prime dividing a_h also divides a_h+1. Put a_h = 3^h+1b_h. Then b_h+1 = b_h(3^2h+1b_h² - 3^h+2b_h + 1). Now (3^2h+1b_h² - 3^h+2b_h + 1) > 1, so it must have some prime factor p > 1. But p cannot be 3 or divide b_h (since (3^2h+1b_h² - 3^h+2b_h + 1) is a multiple of 3b_h plus 1), so b_h+1 has at least one prime factor p > 3 which does not divide b_h. So b_h+1 has at least h distinct prime factors greater than 3, which answers (2) affirmatively. But that is all we need. We can take m in the first paragraph above to be 3²⁰⁰⁰: (1) m has only one distinct prime factor, (2) 2^m + 1 = 3²⁰⁰¹ b₂₀₀₀ has at least 1999 distinct prime factors other than 3, (3) m divides 2^m + 1. Take k to be a product of 1999 distinct prime factors dividing b₂₀₀₀. Then N = km is the required number with exactly 2000 distinct prime factors which divides 2^N + 1. 

Problem B3

A₁A₂A₃ is an acute-angled triangle. The foot of the altitude from A_i is K_i and the incircle touches the side opposite A_i at L_i. The line K₁K₂ is reflected in the line L₁L₂. Similarly, the line K₂K₃ is reflected in L₂L₃ and K₃K₁ is reflected in L₃L₁. Show that the three new lines form a triangle with vertices on the incircle. 

Solution

 

Let O be the centre of the incircle. Let the line parallel to A₁A₂ through L₂ meet the line A₂O at X. We will show that X is the reflection of K₂ in L₂L₃. Let A₁A₃ meet the line A₂O at B₂. Now A₂K₂ is perpendicular to K₂B₂ and OL₂ is perpendicular to L₂B₂, so A₂K₂B₂ and OL₂B₂ are similar. Hence K₂L₂/L₂B₂ = A₂O/OB₂. But OA₃ is the angle bisector in the triangle A₂A₃B₂, so A₂O/OB₂ = A₂A₃/B₂A₃.

Take B'₂ on the line A₂O such that L₂B₂ = L₂B'₂ (B'₂ is distinct from B₂ unless L₂B₂ is perpendicular to the line). Then angle L₂B'₂X = angle A₃B₂A₂. Also, since L₂X is parallel to A₂A₁, angle L₂XB'₂ = angle A₃A₂B₂. So the triangles L₂XB'₂ and A₃A₂B₂ are similar. Hence A₂A₃/B₂A₃ = XL₂/B₂'L₂ = XL₂/B₂L₂ (since B'₂L₂ = B₂L₂).

Thus we have shown that K₂L₂/L₂B₂ = XL₂/B₂L₂ and hence that K₂L₂ = XL₂. L₂X is parallel to A₂A₁ so angle A₂A₁A₃ = angle A₁L₂X = angle L₂XK₂ + angle L₂K₂X = 2 angle L₂XK₂ (isosceles). So angle L₂XK₂ = 1/2 angle A₂A₁A₃ = angle A₂A₁O. L₂X and A₂A₁ are parallel, so K₂X and OA₁ are parallel. But OA₁ is perpendicular to L₂L₃, so K₂X is also perpendicular to L₂L₃ and hence X is the reflection of K₂ in L₂L₃.

Now the angle K₃K₂A₁ = angle A₁A₂A₃, because it is 90^o - angle K₃K₂A₂ = 90^o - angle K₃A₃A₂ (A₂A₃K₂K₃ is cyclic with A₂A₃ a diameter) = angle A₁A₂A₃. So the reflection of K₂K₃ in L₂L₃ is a line through X making an angle A₁A₂A₃ with L₂X, in other words, it is the line through X parallel to A₂A₃.

Let M_i be the reflection of L_i in A_iO. The angle M₂XL₂ = 2 angle OXL₂ = 2 angle A₁A₂O (since A₁A₂ is parallel to L₂X) = angle A₁A₂A₃, which is the angle betwee L₂X and A₂A₃. So M₂X is parallel to A₂A₃, in other words, M₂ lies on the reflection of K₂K₃ in L₂L₃.

If follows similarly that M₃ lies on the reflection. Similarly, the line M₁M₃ is the reflection of K₁K₃ in L₁L₃, and the line M₁M₂ is the reflection of K₁K₂ in L₁L₂ and hence the triangle formed by the intersections of the three reflections is just M₁M₂M₃.