18th USA Mathematical Olympiad 1989 Problems

18th USA Mathematical Olympiad 1989 Problems

1.  Let a_n = 1 + 1/2 + 1/3 + ... + 1/n, b_n = a₁ + a₂ + ... + a_n, c_n = b₁/2 + b₂/2 + ... + b_n/(n+1). Find b₁₉₈₈ and c₁₉₈₈ in terms of a₁₉₈₉.

2.  In a tournament between 20 players, there are 14 games (each between two players). Each player is in at least one game. Show that we can find 6 games involving 12 different players.

3.  A monic polynomial with real coefficients has modulus less than 1 at the complex number i. Show that there is a root z = u + iv (with u and v real) such that (u² + v² + 1)² < 4v² + 1.

4.  An acute-angled triangle has unequal sides. Show that the line through the circumcenter and incenter intersects the longest side and the shortest side.

5.  Which is larger, the real root of x + x² + ... + x⁸ = 8 - 10x⁹, or the real root of x + x² + ... + x¹⁰ = 8 - 10x¹¹?

Solution

18th USA Mathematical Olympiad 1989

Problem 1

Let a_n = 1 + 1/2 + 1/3 + ... + 1/n, b_n = a₁ + a₂ + ... + a_n, c_n = b₁/2 + b₂/2 + ... + b_n/(n+1). Find b₁₉₈₈ and c₁₉₈₈ in terms of a₁₉₈₉.

Solution

Grouping the 1/r terms, we have b_n-1 = (n - 1) + (n/2 - 2/2) + (n/3 - 3/3) + ... + (n/n - n/n) = n a_n - n. Hence, in particular, b₁₉₈₈ = 1989 a₁₉₈₉ - 1989.

Hence also b_m/(m+1) = a_m+1 - 1, so c_n-1 = (a₂ + a₃ + ... + a_n) - (n-1) = b_n - n = (n+1) a_n+1 - (2n+1). But (n+1) a_n+1 = (n+1) a_n + 1, so c_n-1 = (n+1) a_n - 2n. Hence, in particular, c₁₉₈₈ = 1990 a₁₉₈₉ - 3978. Problem 2

In a tournament between 20 players, there are 14 games (each between two players). Each player is in at least one game. Show that we can find 6 games involving 12 different players.

Solution

Call a game a repeat if it is not the first game for both players. There are 28 playing positions available (2 per game) and each of the 20 players takes at least one. So there are at most 8 repeat games. So there are at least 6 games which are not repeats. These must involve 12 different players.

---

Problem 3

A monic polynomial with real coefficients has modulus less than 1 at the complex number i. Show that there is a root z = u + iv (with u and v real) such that (u² + v² + 1)² < 4v² + 1.

Solution

If the polynomial has degree 1, then it is x + a for some a. But then |i + a|² = 1 + a² ≥ 1. Contradiction. So the polynomial has degree 2 or more.

Suppose its degree is even. Then since it has real coefficients, so it must factorise into real monic quadratics. At least one of these must have modulus less than 1 at z = i. Suppose it is x² + ax + b. We have 1 > |-1 + ai + b|² = a² + (b-1)² (*). So b > 0. Also a² < 2b - b² < 2b < 4b. Hence the roots are complex. Suppose they are u ± iv. Then a = -2u, b = u²+v², so (*) gives 4u² + (u² + v² - 1)² < 1. Hence (u² + v² + 1)² = 4u² + 4v² + (u² + v² - 1)² < 1 + 4v².

Similarly, if the degree is odd, then we can factorise it into real monic quadratics and a real linear monic. At least one of these must have modulus less than 1 at z = i. It cannot be the linear monic (by the argument in the first paragraph), so it must be one of the quadratics. We can now argue as above.

---

Problem 4

An acute-angled triangle has unequal sides. Show that the line through the circumcenter and incenter intersects the longest side and the shortest side.

Solution

Let the vertices be A, B, C. Assume AB > BC > CA. Let the circumcenter be O and the incenter be I. Extend the perpendicular from O to BC to meet the circle at M, so that M is the midpoint of the arc BC. Then AM is the angle bisector of A, so passes through I. Since AB > AC, O must lie on the same side of the line AI as B. Similarly, since BA > BC, O must lie on the same side of the line BI as A. So the ray IO lies between the rays IA and IB and hence intersects AB, the longest side.

Similarly, since CB > CA, O must lie on the same side of CI as B. Thus O lies between the rays CI and IB. Hence the ray OI must lie between the rays IC and BI and hence intersect AC, the shortest side.

---

Problem 5

Which is larger, the real root of x + x² + ... + x⁸ = 8 - 10x⁹, or the real root of x + x² + ... + x¹⁰ = 8 - 10x¹¹?

Solution

Answer: the equation of degree 11 has the larger root.

Let f(x) = x + x² + ... + x⁸ + 10x⁹, and g(x) = x + x² + ... + x¹⁰ + 10x¹¹. We have f(x) = (x - x⁹)/(1 - x) + 10x⁹, g(x) = (x - x¹¹)/(1 - x) + 10x¹¹.

Evidently f(x) and g(x) are strictly monotonic increasing for x positive, so f(x) = 8 and g(x) = 8 can each have at most one real root for x positive. Indeed f(0) = g(0) = 0 and f(1) and g(1) are both > 8, so they each have exactly one positive root, which lies between 0 and 1. In fact, it is convenient to be slightly more precise: f(0.9) = (0.9 - 0.9⁹)/0.1 + 10 0.9⁹ = 9 and similarly g(0.9) = 9, so the roots lie between 0 and 0.9.

If x ≤ -1, then |10x⁹| > |x + x² + ... + x⁸|, so f(x) < 0. Similarly g(x). So there are no roots ≤ -1. Finally, for -1 < x < 0, the odd powers of x are negative, so f(x) < x² + x⁴ + x⁶ + x⁸ < 4 < 8. Similarly g(x) < x² + x⁴ + x⁶ + x⁸ + x¹⁰ < 5 < 8. So there are no roots to f(x) = 8 or g(x) = 8 in that range.

Now suppose h is the root to f(h) = 8, we have f(h) = (h - h⁹)/(1 - h) + 10 h⁹ = h/(1 - h) + (10 - 1/(1 - h) ) h⁹. But h < 0.9, so 10 - 1/(1 - h) > 0. But now g(h) = (h - h¹¹)/(1 - h) + 10 h¹¹ = h/(1 - h) + (10 - 1/(1 - h) ) h¹¹ < f(h) = 8. So the root for g(x) = 8 must be larger.

Comment. Arguably, it is not necessary to establish that there are no roots except those between 0 and 1.