20th USA Mathematical Olympiad 1991 Problems

20th USA Mathematical Olympiad 1991 Problems

 

1.  An obtuse angled triangle has integral sides and one acute angle is twice the other. Find the smallest possible perimeter.

2.  For each non-empty subset of {1, 2, ... , n} take the sum of the elements divided by the product. Show that the sum of the resulting quantities is n² + 2n - (n + 1)s_n, where s_n = 1 + 1/2 + 1/3 + ... + 1/n.

3.  Define the function f on the natural numbers by f(1) = 2, f(n) = 2^f(n-1). Show that f(n) has the same residue mod m for all sufficiently large n.

4.  a and b are positive integers and c = (a^a+1 + b^b+1)/(a^a + b^b). By considering (xⁿ - nⁿ)/(x - n) or otherwise, show that c^a + c^b ≥ a^a + b^b.

5.  X is a point on the side BC of the triangle ABC. Take the other common tangent (apart from BC) to the incircles of ABX and ACX which intersects the segments AB and AC. Let it meet AX at Y. Show that the locus of Y, as X varies, is the arc of a circle.

Solution

20th USA Mathematical Olympiad 1991

Problem 1

An obtuse angled triangle has integral sides and one acute angle is twice the other. Find the smallest possible perimeter.

Solution

Answer: 77 = 16 + 28 + 33.

Let the triangle be ABC with angle A obtuse and angle B = 2 angle C. Let the sides be a, b, c as usual. Note that a > b > c. We have b sin C = c sin 2C and c² = a² + b² - 2ab sin C. Hence, b/2c = sin 2C/sin C = cos C = (a² + b² - c²)/2ab. So ab² = a²c + b²c - c³. Hence b²(a - c) = c(a² - c²). Dividing by a - c we get b² = c(a + c).

Now the triangle with smallest perimeter will have a, b, c relatively prime (otherwise we could divide by the common factor). Hence c must be a square. For if c and a+c have a common factor, then so do a and c and hence a, b and c, which means they cannot be the minimal set. Clearly c is not 1 (or the triangle would have nil area). c = 4 gives a = 5, which is too short, or a ≥ 21, which is too long. c = 9 gives a = 7 (too short), 18 (3 divides a, b, c), or ≥ 40 (too long). c = 16 gives a = 20 (too short) or a = 33 which works. Larger c gives a larger perimeter. Eg c = 25 gives a = 56, b = 45 (perimeter 126). Problem 2

For each non-empty subset of {1, 2, ... , n} take the sum of the elements divided by the product. Show that the sum of the resulting quantities is n² + 2n - (n + 1)s_n, where s_n = 1 + 1/2 + 1/3 + ... + 1/n.

Solution

This is a straightforward induction. For n = 1 the only term in the sum is 1/1 with sum 1. The formula gives 1² + 2.1 - 2.1 = 1. So it is true for n = 1.

Note first that for n the sum of the inverses of the products, including 1 for the empty set, is (1 + 1/1)(1 + 1/2)(1 + 1/3) ... (1 + 1/n) = n+1 (it telescopes). Now the sum for n+1 is the sum for n plus the sum of terms involving n+1. But if a term involves n+1, then the sum is increased by n+1 and the product is increased by a factor n+1. So the sum of all the terms involving n+1 is (1/n+1 x sum for n) + (sum of inverse products for n) = (n² + 2n - (n+1)s_n)/(n+1) + (n+1) = n+1 - 1/(n+1) - s_n + (n+1) = 2(n+1) - s_n+1. Hence the sum for n+1 is (n² + 2n) - (n+1)s_n + 2(n+1) - s_n+1 = (n+1)² + 2(n+1) - 1 - (n+1)s_n - s_n+1 = (n+1)² + 2(n+1) - (n+1)/(n+1) - (n+1)s_n - s_n+1 = (n+1)² + 2(n+1) - (n+2)s_n+1.

---

Problem 3

Define the function f on the natural numbers by f(1) = 2, f(n) = 2^f(n-1). Show that f(n) has the same residue mod m for all sufficiently large n.

Solution

This is the so-called tower of exponents, but HTML is not up showing it! The trick is to use induction on m (which is not at all obvious). The result is trivial for m = 1.

If m is even, then we can write m = 2^ab, where b is odd. Then f(n) is eventually constant mod b. Obviously f(n) is eventually 0 mod 2^a, so the residue mod m is eventually constant.

If m is odd, then 2^φ(m) = 1 mod m, where φ(m) < m. So by induction f(n) is eventually constant mod φ(m). Hence f(n+1) = 2^f(n) is eventually constant mod m.

---

Problem 4

a and b are positive integers and c = (a^a+1 + b^b+1)/(a^a + b^b). By considering (xⁿ - nⁿ)/(x - n) or otherwise, show that c^a + c^b ≥ a^a + b^b.

Solution

(xⁿ - nⁿ)/(x - n) = x^n-1 + x^n-2n + ... + n^n-1. If x > n, then each term is > n^n-1, so (xⁿ - nⁿ)/(x - n) > nⁿ. If x < n, then each term is <= nⁿ with equality only for the last term, so (xⁿ - nⁿ)/(x - n) < nⁿ. So multiplying by x - n, which is positive for x > n and negative for x < n, we get (xⁿ - nⁿ) > (x - n)nⁿ except for x = n, and hence (xⁿ - nⁿ) ≥ (x - n)nⁿ for all x ≥ 0.

Putting x = c, n = a, we get (c^a - a^a) ≥ (c - a)a^a. Similarly, putting x = c, n = b, we get (c^b - b^b) ≥ (c - b)b^b. Adding (c^a + c^b) - (a^a + b^b) ≥ (c - a)a^a + (c - b)b^b = c(a^a + b^b) - a^a+1 - b^b+1 = 0, which is the required result.

---

Problem 5

X is a point on the side BC of the triangle ABC. Take the other common tangent (apart from BC) to the incircles of ABX and ACX which intersects the segments AB and AC. Let it meet AX at Y. Show that the locus of Y, as X varies, is the arc of a circle.

Solution

We show that AY = (AB + AC - BC)/2 = constant.

Let the common tangent meet the incircles of ABX, ACX at R, S respectively. Let AX meet them at P, Q respectively and let BC meet them at U, V respectively. Let AB meet the incircle of ABX at K and let AC meet the incircle of ACX at L. We have AY = AQ - QY and AY = AP - PY. So adding 2AY = AP + AQ - (YQ + YP) = AP + AQ - (YS + YR) = AP + AQ - RS. If we reflect about the line of centers of the two incircles R goes to U and S to V. Hence RS = UV. So 2AY = AP + AQ - UV. We have AP = AK = AB - BK = AB - BU and AQ = AL = AC - CL = AC - CV. Hence 2AY = AB + AC - BU - UV - CV = AB + AC - BC.