39th International Mathematical Olympiad 1998 Problems & Solutions

A1. In the convex quadrilateral ABCD, the diagonals AC and BD are perpendicular and the opposite sides AB and DC are not parallel. The point P, where the perpendicular bisectors of AB and DC meet, is inside ABCD. Prove that ABCD is cyclic if and only if the triangles ABP and CDP have equal areas.

A2. In a competition there are a contestants and b judges, where b ≥ 3 is an odd integer. Each judge rates each contestant as either "pass" or "fail". Suppose k is a number such that for any two judges their ratings coincide for at most k contestants. Prove k/a ≥ (b-1)/2b.

A3. For any positive integer n, let d(n) denote the number of positive divisors of n (including 1 and n). Determine all positive integers k such that d(n²) = k d(n) for some n.

B1. Determine all pairs (a, b) of positive integers such that ab² + b + 7 divides a²b + a + b.

B2. Let I be the incenter of the triangle ABC. Let the incircle of ABC touch the sides BC, CA, AB at K, L, M respectively. The line through B parallel to MK meets the lines LM and LK at R and S respectively. Prove that the angle RIS is acute.

B3. Consider all functions f from the set of all positive integers into itself satisfying f(t²f(s)) = s f(t)² for all s and t. Determine the least possible value of f(1998).

Solutions

Problem A1

In the convex quadrilateral ABCD, the diagonals AC and BD are perpendicular and the opposite sides AB and DC are not parallel. The point P, where the perpendicular bisectors of AB and DC meet, is inside ABCD. Prove that ABCD is cyclic if and only if the triangles ABP and CDP have equal areas.

Solution

Let AC and BD meet at X. Let H, K be the feet of the perpendiculars from P to AC, BD respectively. We wish to express the areas of ABP and CDP in terms of more tractable triangles. There are essentially two different configurations possible. In the first, we have area PAB = area ABX + area PAX + area PBX, and area PCD = area CDX - area PCX - area PDX. So if the areas being equal is equivalent to: area ABX - area CDX + area PAX + area PCX + area PBX + area PDX = 0. ABX and CDX are right-angled, so we may write their areas as AX·BX/2 and CX·DX/2. We may also put AX = AH - HX = AH - PK, BX = BK - PH, CX = CH + PK, DX = DK + PH. The other triangles combine in pairs to give area ACP + area BDP = (AC·PH + BD·PK)/2. This leads, after some cancellation to AH·BK = CH·DK. There is a similar configuration with the roles of AB and CD reversed.

The second configuration is area PAB = area ABX + area PAX - PBX, area PCD = area CDX + area PDX - area PCX. In this case AX = AH + PK, BX = BK - PH, CX = CH - PK, DX = DK + PH. But we end up with the same result: AH·BK = CH·DK.

Now if ABCD is cyclic, then it follows immediately that P is the center of the circumcircle and AH = CH, BK = DK. Hence the areas of PAB and PCD are equal.

Conversely, suppose the areas are equal. If PA > PC, then AH > CH. But since PA = PB and PC = PD (by construction), PB > PD, so BK > DK. So AH·BK > CH·DK. Contradiction. So PA is not greater than PC. Similarly it cannot be less. Hence PA = PC. But that implies PA = PB = PC = PD, so ABCD is cyclic.

Problem A2

In a competition there are a contestants and b judges, where b ≥ 3 is an odd integer. Each judge rates each contestant as either "pass" or "fail". Suppose k is a number such that for any two judges their ratings coincide for at most k contestants. Prove k/a ≥ (b-1)/2b.

Solution

Let us count the number N of triples (judge, judge, contestant) for which the two judges are distinct and rate the contestant the same. There are b(b-1)/2 pairs of judges in total and each pair rates at most k contestants the same, so N ≤ kb(b-1)/2.

Now consider a fixed contestant X and count the number of pairs of judges rating X the same. Suppose x judges pass X, then there are x(x-1)/2 pairs who pass X and (b-x)(b-x-1)/2 who fail X, so a total of (x(x-1) + (b-x)(b-x-1))/2 pairs rate X the same. But (x(x-1) + (b-x)(b-x-1))/2 = (2x² - 2bx + b² - b)/2 = (x - b/2)² + b²/4 - b/2 ≥ b²/4 - b/2 = (b - 1)²/4 - 1/4. But (b - 1)²/4 is an integer (since b is odd), so the number of pairs rating X the same is at least (b - 1)²/4. Hence N ≥ a (b - 1)²/4. Putting the two inequalities together gives k/a ≥ (b - 1)/2b.

Problem A3

For any positive integer n, let d(n) denote the number of positive divisors of n (including 1 and n). Determine all positive integers k such that d(n²) = k d(n) for some n.

Solution

Let n = p₁^a₁...p_r^a_r. Then d(n) = (a₁ + 1)(a₂ + 1) ... (a_r + 1), and d(n²) = (2a₁ + 1)(2a₂ + 1) ... (2a_r + 1). So the a_i must be chosen so that (2a₁ + 1)(2a₂ + 1) ... (2a_r + 1) = k (a₁ + 1)(a₂ + 1) ... (a_r + 1). Since all (2a_i + 1) are odd, this clearly implies that k must be odd. We show that conversely, given any odd k, we can find a_i.

We use a form of induction on k. First, it is true for k = 1 (take n = 1). Second, we show that if it is true for k, then it is true for 2^mk - 1. That is sufficient, since any odd number has the form 2^mk - 1 for some smaller odd number k. Take a_i = 2ⁱ((2^m - 1)k - 1) for i = 0, 1, ... , m-1. Then 2a_i + 1 = 2ⁱ⁺¹(2^m - 1)k - (2ⁱ⁺¹ - 1) and a_i + 1 = 2ⁱ(2^m - 1)k - (2ⁱ - 1). So the product of the (2a_i + 1)'s divided by the product of the (a_i + 1)'s is 2^m(2^m - 1)k - (2^m - 1) divided by (2^m - 1)k, or (2^mk - 1)/k. Thus if we take these a_is together with those giving k, we get 2^mk - 1, which completes the induction.

Problem B1

Determine all pairs (a, b) of positive integers such that ab² + b + 7 divides a²b + a + b.

Answer (a, b) = (11, 1), (49, 1) or (7k², 7k).

Solution

If a < b, then b ≥ a + 1, so ab² + b + 7 > ab² + b ≥ (a + 1)(ab + 1) = a²b + a + ab ≥ a²b + a + b. So there can be no solutions with a < b. Assume then that a ≥ b.

Let k = the integer (a²b + a + b)/(ab² + b + 7). We have (a/b + 1/b)(ab² + b + 7) = ab² + a + ab + 7a/b + 7/b + 1 > ab² + a + b. So k < a/b + 1/b. Now if b ≥ 3, then (b - 7/b) > 0 and hence (a/b - 1/b)(ab² + b + 7) = ab² + a - a(b - 7/b) - 1 - 7/b < ab² + a < ab² + a + b. Hence either b = 1 or 2 or k > a/b - 1/b.

If a/b - 1/b < k < a/b + 1/b, then a - 1 < kb < a + 1. Hence a = kb. This gives the solution (a, b) = (7k², 7k).

It remains to consider b = 1 and 2. If b = 1, then a + 8 divides a² + a + 1 and hence also a(a + 8) - (a² + a + 1) = 7a - 1, and hence also 7(a + 8) - (7a - 1) = 57. The only factors bigger than 8 are 19 and 57, so a = 11 or 49. It is easy to check that (a, b) = (11, 1) and (49, 1) are indeed solutions.

If b = 2, then 4a + 9 divides 2a² + a + 2, and hence also a(4a + 9) - 2(2a² + a + 2) = 7a - 4, and hence also 7(4a + 9) - 4(7a - 4) = 79. The only factor greater than 9 is 79, but that gives a = 35/2 which is not integral. Hence there are no solutions for b = 2.

A variant on this from Johannes Tang Lek Huo is as follows:

We have ab² + b + 7 divides a(ab² + b + 7) - b(a²b + a + b) = 7a - b² . If 7a = b², then b must be a multiple of 7, so b = 7k for some k. Then a = 7k², and it is easy to check that this is a solution. We cannot have 7a < b² for then 0 < b² - 7a < ab² < ab² + b + 7. If 7a > b, then we must have 7a - b ≤ ab² + b + 7 > ab², so 7 > b², so b = 1 or 2.

We can then continue as above.

Problem B2

Let I be the incenter of the triangle ABC. Let the incircle of ABC touch the sides BC, CA, AB at K, L, M respectively. The line through B parallel to MK meets the lines LM and LK at R and S respectively. Prove that the angle RIS is acute.

Solution

We show that RI² + SI² - RS² > 0. The result then follows from the cosine rule.

BI is perpendicular to MK and hence also to RS. So IR² = BR² + BI² and IS² = BI² + BS². Obviously RS = RB + BS, so RS² = BR² + BS² + 2 BR·BS. Hence RI² + SI² - RS² = 2 BI² - 2 BR·BS. Consider the triangle BRS. The angles at B and M are 90 - B/2 and 90 - A/2, so the angle at R is 90 - C/2. Hence BR/BM = cos A/2/cos C/2 (using the sine rule). Similarly, considering the triangle BKS, BS/BK = cos C/2/cos A/2. So BR·BS = BM·BK = BK². Hence RI² + SI² - RS² = 2(BI² - BK²) = 2 IK² > 0.

Problem B3

Consider all functions f from the set of all positive integers into itself satisfying f(t²f(s)) = s f(t)² for all s and t. Determine the least possible value of f(1998).

Answer

120

Solution

Let f(1) = k. Then f(kt²) = f(t)² and f(f(t)) = k²t. Also f(kt)² = 1·f(kt)² = f(k³t²) = f(1²f(f(kt²))) = k²f(kt²) = k²f(t)². Hence f(kt) = k f(t).

By an easy induction kⁿf(tⁿ⁺¹) = f(t)ⁿ⁺¹. But this implies that k divides f(t). For suppose the highest power of a prime p dividing k is a > b, the highest power of p dividing f(t). Then a > b(1 + 1/n) for some integer n. But then na > (n + 1)b, so kⁿ does not divide f(t)ⁿ⁺¹. Contradiction.

Let g(t) = f(t)/k. Then f(t²f(s)) = f(t²kg(s)) = k f(t²g(s) = k²g(t²g(s)), whilst s f(t)² = k²s f(t)². So g(t²g(s)) = s g(t)². Hence g is also a function satisfying the conditions which evidently has smaller values than f (for k > 1). It also satisfies g(1) = 1. Since we want the smallest possible value of f(1998) we may restrict attention to functions f satisfying f(1) = 1.

Thus we have f(f(t) = t and f(t²) = f(t)². Hence f(st)² = f(s²t²) = f(s²f(f(t²))) = f(s)²f(t²) = f(s)²f(t)². So f(st) = f(s) f(t).

Suppose p is a prime and f(p) = m·n. Then f(m)f(n) = f(mn) = f(f(p)) = p, so one of f(m), f(n) = 1. But if f(m) = 1, then m = f(f(m)) = f(1) = 1. So f(p) is prime. If f(p) = q, then f(q) = p.

Now we may define f arbitarily on the primes subject only to the conditions that each f(prime) is prime and that if f(p) = q, then f(q) = p. For suppose that s = p₁^a₁...p_r^a_r and that f(p_i) = q_i. If t has any additional prime factors not included in the q_i, then we may add additional p's to the expression for s so that they are included (taking the additional a's to be zero). So suppose t = q₁^b₁...q_r^b_r.Then t²f(s) = q₁^2b₁+a₁ ...q_r^2b_r+a_r and hence f(t²f(s) = p₁^2b₁+a₁ ...p_r^2b_r+a_r = s f(t)².

We want the minimum possible value of f(1998). Now 1998 = 2.3³.37, so we achieve the minimum value by taking f(2) = 3, f(3) = 2, f(37) = 5 (and f(37) = 5). This gives f(1998) = 3·2³5 = 120.