22nd USA Mathematical Olympiad 1993 Problems
1. n > 1, and a and b are positive real numbers such that an - a - 1 = 0 and b2n - b - 3a = 0. Which is larger?
2. The diagonals of a convex quadrilateral meet at right angles at X. Show that the four points obtained by reflecting X in each of the sides are cyclic.
3. Let S be the set of functions f defined on reals in the closed interval [0, 1] with non-negative real values such that f(1) = 1 and f(x) + f(y) ≤ f(x + y) for all x, y such that x + y ≤ 1. What is the smallest k such that f(x) ≤ kx for all f in S and all x?
4. The sequence an of odd positive integers is defined as follows: a1 = r, a2 = s, and an is the greatest odd divisor of an-1 + an-2. Show that, for sufficiently large n, an is constant and find this constant (in terms of r and s).
5. A sequence xn of positive reals satisfies xn-1xn+1 ≤ xn2. Let an be the average of the terms x0, x1, ... , xn and bn be the average of the terms x1, x2, ... , xn. Show that anbn-1 ≥ an-1bn.
Solution
22nd USA Mathematical Olympiad 1993
Problem 1
n > 1, and a and b are positive real numbers such that an - a - 1 = 0 and b2n - b - 3a = 0. Which is larger?
Solution
Answer: a > b.
Note that an = a + 1 > 1 (since a is positive). Hence a > 1. So a2n = (a + 1)2 = a2 + 2a + 1. Put a = 1 + k, then a2 = 1 + 2k + k2 > 1 + 2k, so a2 + 1 > 2 + 2k = 2a. Hence a2n > 4a. So (b/a)2n = (b + 3a)/a2n < (b + 3a)/4a. If b/a ≥ 1, then (b + 3a)/4a ≤ (b + 3b)/4a = b/a, so (b/a)2n < b/a. Contradiction. Hence b/a < 1. Problem 2
The diagonals of a convex quadrilateral meet at right angles at X. Show that the four points obtained by reflecting X in each of the sides are cyclic.
Solution
If we shrink the reflected points by 1/2 about the point X, then we get the feet of the perpendiculars from X to the sides. So it is sufficient to show that these four points are cyclic. Let the quadrilateral be ABCD. Let the feet of the perpendiculars from X to AB, BC, CD, DA be P, Q, R, S respectively.
XPBQ is cyclic, so ∠XQP = ∠XBP. Similarly, XPAS is cyclic, so ∠XSP = ∠XAP. But XBP and XAP are two angles in the triangle XAB and the third is ∠AXB = 90o. Hence ∠XQP + ∠XSP = 90o. Similarly ∠XQR + ∠XSR = 90o. Adding, ∠PQR + ∠PSR = 180o, so PQRS is cyclic.
Let S be the set of functions f defined on reals in the closed interval [0, 1] with non-negative real values such that f(1) = 1 and f(x) + f(y) ≤ f(x + y) for all x, y such that x + y ≤ 1. What is the smallest k such that f(x) ≤ kx for all f in S and all x?
Solution
Answer: k = 2.
Consider the function f(x) = 0 for 0 ≤ x ≤ 1/2, 1 for 1/2 < x ≤ 1. If x + y ≤ 1, then at least one of x, y is ≤ 1/2, so at least one of f(x), f(y) is 0. But f is obviously increasing, so the other of f(x), f(y) is ≤ f(x + y). Thus f satisfies the conditions. But f(1/2 + ε) = 1, so k cannot be smaller than 2.
So now let f be any function satisfying the conditions. We wish to show that f(x) ≤ 2x. Putting y = 1-x, we get f(x) + f(y) <= f(1) = 1. But f(y) is non-negative, so f(x) ≤ 1. Put y = x ≤ 1/2. Then 2f(x) ≤ f(2x). A simple induction gives 2nf(x) ≤ f(2nx) for x ≤ 1/2n. Now take any x in [0, 1]. If x > 1/2, then 2x > 1, so f(x) < 2x. If x ≤ 1/2, choose n ≥ 1, so that 1/2n+1 < x ≤ 1/2n. Then 2nf(x) ≤ f(2nx) ≤ 1, so f(x) ≤ 1/2n ≤ 2x.
The sequence an of odd positive integers is defined as follows: a1 = r, a2 = s, and an is the greatest odd divisor of an-1 + an-2. Show that, for sufficiently large n, an is constant and find this constant (in terms of r and s).
Solution
This is awkward to get started. Note that if an-1 = an-2, then an-1 + an-2 = 2an-1, whose greatest odd divisor is just an-1, so an = an-1. So once two consecutive terms are constant the following terms are constant.
Both an-1 and an-2 are odd, so an-1 + an-2 is even and hence an ≤ (an-1 + an-2)/2. So if an-1 and an-2 are unequal, then an < max(an-1, an-2). As already noted, if they are equal, then an = max(an-1, an-2).
Put bn = max(an, an-1). If an < an-1, then an+1 < max(an, an-1) = an-1. Also an+2 ≤ max(an+1, an) < an-1. Hence max(an+2, an+1) < max(an, an-1) or bn+2 < bn. If an > an-1, then an+1 < max(an, an-1) = an, and an+2 < max(an+1, an) = an. Hence bn+2 < bn. Thus if an and an-1 are unequal, then bn+2 < bn. But obviously an > 0 for all n, and so bn > 0 for all n. Also it is integral, and b1 = max(r, s), so we can only have b2n+1 < b2n-1 for at most max(r, s) values of n. Hence for some n we must have an = an-1 and then an is constant from that point on.
We show that the constant is the greatest common divisor of r and s. Use parentheses to denote the greatest common divisor, so the greatest common divisor of r and s is (r, s). We have (an-1, an-2) = (an-1, an-1 + an-2) = (an, an-1). So if an is constant for n ≥ N, we have (r, s) = (a1, a2) = (a2, a3) = ... = (aN, aN+1) = aN. We claim that an = d for n > 3. Clearly d divides r + s and hence d divides a3. But d divides a2 = s, so d also divides a2 + a3 and hence d divides a4. Now suppose some odd k divides r + s, but does not divide s. So k divides a3, but not a2. Hence it does not divide a4.
A sequence xn of positive reals satisfies xn-1xn+1 ≤ xn2. Let an be the average of the terms x0, x1, ... , xn and bn be the average of the terms x1, x2, ... , xn. Show that anbn-1 ≥ an-1bn.
Solution
Put k = x1 + x2 + ... + xn-1. We have to show that (x0 + k + xn)/(n+1) k/(n-1) ≥ (x0 + k)/n (k + xn)/n or n2(k + x0 + xn) ≥ (n2 - 1)(k + x0)(k + xn). Simplifying slightly, this is equivalent to k(k + x0 + xn) ≥ (n2 - 1)x0xn. So it is evidently sufficient to show that k ≥ (n-1)(x0xn)1/2. [Then AM/GM gives x0 + xn ≥ 2(x0xn)1/2, so (k + x0 + xn) ≥ (n+1)(x0xn)1/2.]
We have x0/x1 ≤ x1/x2 ≤ ... ≤ xn-1/xn. Hence (apparently weakening) x0xn ≤ x1xn-1 ≤ x2xn-2 ≤ ... . So k = (x1 + xn-1) + (x2 + xn-2) + ... ≥ (n-1) (x0xn)1/2, using first AM/GM, then the relation just established.
Labels:
USAMO
Previous Article
