17th USA Mathematical Olympiad 1988 Problems

17th USA Mathematical Olympiad 1988 Problems

1.  The repeating decimal 0.ab ... k pq ... u = m/n, where m and n are relatively prime integers, and there is at least one decimal before the repeating part. Show that n is divisible by 2 or 5 (or both). [For example, 0.01136 = 0.01136363636 ... = 1/88 and 88 is divisible by 2.]

2.  The cubic x³ + ax² + bx + c has real coefficients and three real roots r ≥ s ≥ t. Show that k = a² - 3b ≥ 0 and that √k <= r - t.

3.  Let X be the set {1, 2, ... , 20} and let P be the set of all 9-element subsets of X. Show that for any map f: P → X we can find a 10-element subset Y of X, such that f(Y - {k}) ≠ k for any k in Y.

4.  ABC is a triangle with incenter I. Show that the circumcenters of IAB, IBC, ICA lie on a circle whose center is the circumcenter of ABC.

5.  Let p(x) be the polynomial (1 - x)^a (1 - x²)^b (1 - x³)^c ... (1 - x³²)^k, where a, b, ..., k are integers. When expanded in powers of x, the coefficient of x¹ is -2 and the coefficients of x², x³, ... , x³² are all zero. Find k.

Solution

17th USA Mathematical Olympiad 1988

Problem 1

The repeating decimal 0.ab ... k pq ... u = m/n, where m and n are relatively prime integers, and there is at least one decimal before the repeating part. Show that n is divisible by 2 or 5 (or both). [For example, 0.01136 = 0.01136363636 ... = 1/88 and 88 is divisible by 2.]

Solution

Note that k and u are not equal (otherwise we should have regarded the repeating part as starting at k). We have m/n = ab...k/10^r pq...u/(10^r(10^s - 1) ) = (ab...k (10^s - 1) + pq...u)/(10^r(10^s - 1) ). The numerator = u - k mod 10, which is non-zero, so the numerator is not divisible by 10. But the denominator is divisible by 10. Hence after reduction to lowest terms the denominator is divisible by 2 or 5 or both. Problem 2

The cubic x³ + ax² + bx + c has real coefficients and three real roots r ≥ s ≥ t. Show that k = a² - 3b ≥ 0 and that √k ≤ r - t.

Solution

a² - 3b = (r + s + t)² - 3(rs + st + tr) = r² + s² + t² - (rs + st + tr). By Cauchy-Schwartz we have (rs + st + tr)² ≤ (r² + s² + t²)², so r² + s² + t² ≥ |rs + st + tr| ≥ (rs + st + tr). Hence a² - 3b ≥ 0.

a² - 3b ≤ (r - t)² is the same as r² + s² + t² - rs - st - tr ≤ r² - 2rt + t^s or s² + rt - rs - st ≤ 0 or (r - s)(s - t) ≥ 0, which is true since r ≥ s and s ≥ t. So a² - 3b ≤ (r - t)². Taking the non-negative square roots, we get the required result.

---

Problem 3

Let X be the set {1, 2, ... , 20} and let P be the set of all 9-element subsets of X. Show that for any map f: P → X we can find a 10-element subset Y of X, such that f(Y - {k}) ≠ k for any k in Y.

Solution

Consider pairs (S, k) with S in P and k in X such that f(S) = k. There are evidently 20C9 such pairs, since we can choose any S and k is then fixed. Now consider the pairs (Y, k) such that Y is a 10-element subset of X containing k and f(Y - {k}) = k. The map (Y, k) to (Y - {k}, k) is an injection because if (Y - {k}, k) = (Y' - {k'}, k'), then k = k' and hence Y = Y'. It is not necessarily a bijection because if there are any pairs (S, k) with k in S then they do not correspond to any (Y, k). But certainly the number of pairs (Y, k) is at most the number of pairs (S, k). So there are at most 20C9 pairs (Y, k). But there are 20C10 subsets Y with 10 elements, so at least 20C10 - 20C9 of them (more than 16000) do not belong to any pairs (Y, k), in other words they are such that f(Y - {k}) is not k for any k in Y.

---

Problem 4

ABC is a triangle with incenter I. Show that the circumcenters of IAB, IBC, ICA lie on a circle whose center is the circumcenter of ABC.

Solution

In fact they lie on the circumcircle of ABC.

Extend AI to meet the circumcircle again at A'. We show that A' is the circumcenter of BCI. Angle A'AC = angle A'AB, so A' is the midpoint of the arc BC, so A'B = A'C. Also ∠A'CB = ∠A'AB = A/2, so ∠A'CI = A/2 + B/2. But ∠A'IC = ∠IAC + ∠ICA = A/2 + B/2, so A'CI is isosceles, so A'C = A'I.

---

Problem 5

Let p(x) be the polynomial (1 - x)^a (1 - x²)^b (1 - x³)^c ... (1 - x³²)^k, where a, b, ..., k are integers. When expanded in powers of x, the coefficient of x¹ is -2 and the coefficients of x², x³, ... , x³² are all zero. Find k.

Solution

Answer: 2²⁷ - 2¹¹.

We have p(x) = 1 - 2x + O(x³³). Hence p(-x) = 1 + 2x + O(x³³). Multiplying p(x)p(-x) = 1 - 2²x² + O(x³³). Now p(x) p(-x) cannot have any odd terms, so we can write it as a polynomial in x², q(x²). Hence q(x²) = 1 - 2²x² + O(x³⁴). Similarly, r(x⁴) = q(x²) q(-x²) = 1 - 2⁴x⁴ + O(x³⁶), s(x⁸) = r(x⁴) r(-x⁴) = 1 - 2⁸x⁸ + O(x⁴⁰), and t(x¹⁶) = 1 - 2¹⁶x¹⁶ + O(x⁴⁸).

Now go back to the definition of p(x). When we take p(x) p(-x), the term (1 - x)^a becomes (1 - x²)^a. All the even terms just double their exponent, so (1 - x²)^b becomes (1 - x²)^2b, (1 - x⁴)^d becomes (1 - x⁴)^2d and so on. The odd terms all keep the same exponent, so (1 - x³)^c becomes (1 - x⁶)^c and so on. Thus we get t(x¹⁶) = (1 - x¹⁶)ⁿ(1 - x³²)^16k ... . The first exponent is a sum of several exponents from p(x), but the details are unimportant. We know that t(x¹⁶) = 1 - 2¹⁶x¹⁶ + O(x⁴⁸). The x¹⁶ term can only come from (1 - x¹⁶)ⁿ, so n = 2¹⁶. Now there is no x³² term, so putting N = 2¹⁶ we have NC2 = 16k, were NC2 is the binomial coefficient N(N -1)/2 = 2³¹ - 2¹⁵. Hence k = 2²⁷ - 2¹¹.