16th USA Mathematical Olympiad 1987 Problems
1. Find all solutions to (m2 + n)(m + n2) = (m - n)3, where m and n are non-zero integers.
2. The feet of the angle bisectors of the triangle ABC form a right-angled triangle. If the right-angle is at X, where AX is the bisector of angle A, find all possible values for angle A.
3. X is the smallest set of polynomials p(x) such that: (1) p(x) = x belongs to X; and (2) if r(x) belongs to X, then x r(x) and (x + (1 - x) r(x) ) both belong to X. Show that if r(x) and s(x) are distinct elements of X, then r(x) ≠ s(x) for any 0 < x < 1.
4. M is the midpoint of XY. The points P and Q lie on a line through Y on opposite sides of Y, such that |XQ| = 2|MP| and |XY|/2 < |MP| < 3|XY|/2. For what value of |PY|/|QY| is |PQ| a minimum?
5. a1, a2, ... , an is a sequence of 0s and 1s. T is the number of triples (ai, aj, ak) with i < j < k which are not equal to (0, 1, 0) or (1, 0, 1). For 1 ≤ i ≤ n, f(i) is the number of j < i with aj = ai plus the number of j > i with aj ≠ ai. Show that T = f(1) (f(1) - 1)/2 + f(2) (f(2) - 1)/2 + ... + f(n) (f(n) - 1)/2. If n is odd, what is the smallest value of T?
Solution
16th USA Mathematical Olympiad 1987
Problem 1
Find all solutions to (m2 + n)(m + n2) = (m - n)3, where m and n are non-zero integers.
Solution
Answer: (m, n) = (-1, -1), (8, -10), (9, -6), (9, -21).
If m, n > 0, then lhs is certainly positive, so we must have m > n to make the rhs positive. But then m2 + n > m2 and n2 + m > m, so lhs > m3 > rhs. Contradiction. So there are no solutions with m and n both positive.
Put M = |m|, N = |n|. Consider next m = M, n = -N. So we have (M2 - N)(N2 + M) = (M + N)3. Hence M2N2 + M3 - N3 - MN = M3 + 3M2N + 3MN2 + N3. N is non-zero, so we can divide to get: 2N2 + N(3M - M2) + 3M2 + M = 0. Regarding this as a quadratic in N we solve, getting N = ( (M2 - 3M) ± √(M4 - 6M3 + 9M2 - 24M2 - 8M) )/4 . Thus M4 - 6M3 - 15M2 - 8M = M(M - 1)2(M - 8) must be a square. Hence M(M - 8) must be a square. We have (M - 4)2 = M(M - 8) + 16 and for M ≥ 13, we have (M - 5)2 = M2 - 10M + 25 < M2 - 8M. So we need only consider M ≤ 12. But obviously we cannot have M < 8, or M(M - 8) is negative. Checking the remaining values, we find M = 8 and 9 are the only solutions. They give the solutions (m, n) = (8, -10), (9, -6), (9, -21).
Next, consider the case m = -M, n = N. That clearly does not work. We get (M2 + N)(N2 - M) = - (M + N)3. So 2N2 + (M2 + 3M)N + 3M2 - M = 0, which has no solutions because 3M2 > M.
Finally, consider the case m = -M, n = -N. Then we get (M2 - N)(N2 - M) = (N - M)3, so 2N2 - (M2 + 3M)N + (3M2 - M) = 0. Solving for N, we get N = ( (M2 + 3M) ± √(M4 + 6M3 + 9M2 - 24M2 + 8M) )/4. So we require M(M3 + 6M2 - 15M + 8) = M(M + 8)(M - 1)2 to be a square. Hence M(M + 8) is a square. We have (M + 4)2 > M(M + 8) and for M ≥ 5, we have (M + 3)2 = M2 + 6M + 9 < M2 + 8M. So we need only check M = 1, 2, 3, 4. We find M = 1 gives the only square, and that gives the solution (m, n) = (-1, -1). Problem 2
The feet of the angle bisectors of the triangle ABC form a right-angled triangle. If the right-angle is at X, where AX is the bisector of angle A, find all possible values for angle A.
Solution
Answer: 120o.
Thanks to Richard Rusczyk for this vector solution
Use vectors origin A. Write the vector AB as B etc. Using the familiar BX/CX = AB/AC etc, we have Z = bB/(a+b), Y = cC/(a+c), X = (bB+cC)/(b+c). Hence Z-X = bB(c-a)/((a+b)(b+c)) - cC/(b+c), Y-X = -bB/(b+c) + cC(b-a)/((a+c)(b+c)).
We have (Z-X).(Y-X) = 0, so after multiplying through by (a+b)(a+c)(b+c)2, we get b2B2(a2-c2) + c2C2(a2-b2) + 2bcB.C (a2+bc) = 0. But B2 = c2, C2 = b2, so bc(2a2-b2-c2) + 2B.C (a2+bc) = 0.
But a2 = b2 + c2 - 2B.C (cosine rule), so 2a2-b2-c2 = a2-2B.C. Hence bc(a2-2B.C) + 2B.C(a2+bc) = 0, so B.C = -bc/2. Hence cos A = -1/2, so ∠A = 120o.
One can get there by straight algebra, but my first attempt was a horrendous slog:
Put a = BC, b = CA, c = AB as usual. We have XY2 = CX2 + CY2 - 2 CX.CY cos C. Using the fact that CY/AY = BC/AB, we have CY = ab/(a + c). Similarly, CX = ab/(b + c). Also 2ab cos C = (a2 + b2 - c2). So XY2 = (ab)2/(b+c)2 + (ab)2/(a+c)2 - ab(a2 + b2 - c2)/( (b+c)(a+c) ). So (a+b)2(b+c)2(c+a)2 XY2 = (ab)2(a+b)2(c+a)2 + (ab)2(a+b)2(b+c)2 - ab(a2+b2-c2)(a+b)2(b+c)(c+a) = -a6bc - a5bc2 - a5b2c + 2a4b3c + a4b2c2 + a4bc3 + 2a3b4c + 4a3b3c2 + 3a3b2c3 + a3bc4 - a2b5c + a2b4c2 + 3a2b3c3 + 2a2b2c4 - ab6c - ab5c2 + ab4c3 + ab3c4.
Similarly, we get (a+b)2(b+c)2(c+a)2ZX2 = (ac)2(b+c)2(c+a)2 + (ac)2(a+b)2(c+a)2 - ac(a2+c2-b2)(a+b)(b+c)(c+a)2 = -a6bc - a5b2c - a5bc2 + a4b3c + a4b2c2 + 2a4bc3 + a3b4c + 3a3b3c2 + 4a3b2c3 + 2a3bc4 + 2a2b4c2 + 3a2b3c3 + a2b2c4 - a2bc5 + ab4c3 + ab3c4 - ab2c5 - abc6.
Similarly, (a+b)2(b+c)2(c+a)2YZ2 = (bc)2(b+c)2(c+a)2 + (bc)2(a+b)2(b+c)2 - bc(b2+c2-a2)(b+c)2(a+b)(c+a) = a4b3c + 2a4b2c2 + a4bc3 + a3b4c + 3a3b3c2 + 3a3b2c3 + a3bc4 - a2b5c + a2b4c2 + 4a2b3c3 + a2b2c4 - a2bc5 - ab6c - ab5c2 + 2ab4c3 + 2ab3c4 - ab2c5 - abc6.
But YZ2 - XY2 - ZX2 = 0. So 2a6bc + 2a5b2c + 2a5bc2 - 2a4b3c - 2a4bc3 - 2a3b4c - 4a3b3c2 - 4a3b2c3 - 2a3bc4 - 2a2b4c2 - 2a2b3c3 - 2a2b2c4 = 0.
Factorising, we get 2a2bc(ab + bc + ca)(a2 - b2 - c2 - bc) = 0. Hence a2 = b2 + c2 + bc. But a2 = b2 + c2 - 2bc cos A. Hence cos A = -1/2, so A = 1200. Indeed we have established that this is a necessary and sufficient condition for ∠YXZ = 90o.
Does anyone have a geometric solution?
X is the smallest set of polynomials p(x) such that: (1) p(x) = x belongs to X; and (2) if r(x) belongs to X, then x r(x) and (x + (1 - x) r(x) ) both belong to X. Show that if r(x) and s(x) are distinct elements of X, then r(x) ≠ s(x) for any 0 < x < 1.
Solution
If they are never equal, then we must be able to order them, so that r(x) > s(x) for all x in (0, 1) or s(x) > r(x) for all x in (0, 1). Let us use the notation [+ - - + ... ]. The operation r(x) to x r(x) is denoted as - , and the operation r(x) to x + (1 - x) r(x) is denoted as + . Then the operations are listed in reverse order with the last carried out put first. So for example [ + - ] means we first apply - to get x2, then + to get x + (1 - x)x2 = x + x2 - x3. We claim that we have the ordering + > nothing > - , which we apply starting with the first term. So looking at the first few polynomials we have: [ + + ] > [ + ], because we compare the first terms which are equal, then we compare the second terms. We regard [ + ] as having nothing for the second term, so + > nothing. Then [ + ] > [ + - ], because they have equal first terms, but unequal second terms (nothing > - ). The starting polynomial is represented as [ ]. So we have [ + - ] > [ ] because + > nothing. Then [ ] > [ - + ] > [ - ] > [ - - ]. Clearly this ordering, which is a type of lexicographic ordering is a total order, that is, for any two distinct polynomials in X we will find that one is larger than the other.
So suppose r(x) belongs to the set X. We have to establish that + > nothing > - . In other words, that x + (1 - x) r(x) > x and that x > x r(x). But that is obvious, because by a trivial induction we have 0 < r(x) < 1 for all r(x) in X and x in (0, 1). So, if follows that if r(x) and s(x) are in X then x + (1 - x) r(x) > x s(x). It is also obvious that if [ a ] > [ b ], where a and b are some strings of + and - , then [ + a ] > [ + b ] and [ - a ] > [ - b ]. But that is sufficient to establish the ordering.
M is the midpoint of XY. The points P and Q lie on a line through Y on opposite sides of Y, such that |XQ| = 2|MP| and |XY|/2 < |MP| < 3|XY|/2. For what value of |PY|/|QY| is |PQ| a minimum?
Solution
Let the angle between the line through Y and XY be θ. Take Y' on the line such that XY' = XY. If P is on the opposite side of Y to Y', then Q is on the opposite side of Y' to Y. As P approaches Y, Q approaches Y' so the minimum value of PQ is YY', corresponding to PY/QY = 0. But it is unrealised, since the problem requires MY < MP. If P is on the same side of Y as Y', then as P approaches the midpoint of YY', Q approaches Y. So the minimum value of PQ is YY'/2 with PY/QY = infinity. Again it is unrealised because the problem requires MY < MP. P is allowed to be on either side of Y, so the unrealised minimum value of PQ is YY'/2 as PY/QY approaches infinity.
Comment. This seems too easy. Also the condition MP < 3XY/2 is not used. Is the question correctly stated?
a1, a2, ... , an is a sequence of 0s and 1s. T is the number of triples (ai, aj, ak) with i < j < k which are not equal to (0, 1, 0) or (1, 0, 1). For 1 ≤ i ≤ n, f(i) is the number of j < i with aj = ai plus the number of j > i with aj ≠ ai. Show that T = f(1) (f(1) - 1)/2 + f(2) (f(2) - 1)/2 + ... + f(n) (f(n) - 1)/2. If n is odd, what is the smallest value of T?
Solution
For n odd, the smallest value of T is n(n-1)(n-3)/8 achieved by 01010... 010.
Suppose a particular ai = 0. Let Si be the set of aj with j < i and aj = ai and aj with j > i and aj ≠ ai. Suppose we take any two members of Si and consider the triple formed with ai itself. Surprisingly perhaps, they are all of the required form (ai is bold):
... 0 ... 0 ... 0
... 0 ... 0 ... 1
... 0 ... 1 ... 1
Similarly, if ai = 1:
... 1 ... 1 ... 1
... 1 ... 1 ... 0
... 1 ... 0 ... 0
Conversely, any triple of the required form can be considered (uniquely) to be an ai with members of the triple before it equal to it and members of the triple after it unequal to it. Since f(m) ( f(m) - 1) is the number of ways of choosing two items from f(m), we have established that T = ∑ f(m) ( f(m) - 1). We show that ∑ f(m) = n(n-1)/2 (and is hence independent of the details of the particular sequence ai - it depends only on its length). In the case of a sequence of all 0s, we have f(1) = 0, f(2) = 1, ... , f(n) = n-1, so ∑ f(m) = n(n-1)/2. Now suppose we have a particular sequence and we change ai from 0 to 1. Suppose there are a 0s before ai, b 1s before ai, c 0s after ai and d 1s after ai. Then the value of f(i) is changed from a + d to b + c, an increase of (b - a) + (c - d). The value of f(j) with j < i is decreased by 1 if f(j) is 0 and increased by 1 if f(j) is 0. So in total there is an increase of (a - b) for such j. Similarly, for j > i, the value of f(j) is decreased by 1 if f(j) is 0 and increased by 1 if f(j) is 1, a net increase of (d - c). Thus overall ∑ f(m) is increased by (b - a) + (c - d) + (a - b) + (d - c) = 0. But by a sequence of such changes we can get to any sequence ai, so all sequences (of length n) have the same value for ∑ f(m).
Thus T is minimised when ∑ f(m)2 is minimised. But since ∑ f(m) is fixed, that is achieved when the f(m) are as equal as possible. If n =2k+1, then ∑ f(m) = n(n-1)/2, so the average value of f(m) is exactly k, so we look for an arrangement with all f(m) = k. It is not hard to see that 01010...1010 works. So this gives T = ∑ k(k-1)/2 = n(n-1)(n-3)/8.
The question does not ask for it, but the even case is also straightforward. If n = 2k, then the best we can hope for is k values of k and k values of k-1, so that ∑ f(m) = k.k + k.(k-1) = k(2k-1) = n(n-1)/2. That is achieved by 0101...0101 (all the 0s have f(m) = k and all the 1s have f(m) = k-1). Hence T = k.k(k-1)/2 + (k-1).(k-1)(k-2)/2 = (k-1)(2k2-3k+2)/2 = (n-2)(n2-3n+4)/8.
Labels:
USAMO
Previous Article
